MO417 - Questão para a prova oral 

Número:

Enunciado: Analise o algoritmo responsável por encontrar a maior subsequência comum e responda qual a alternativa que representa o tamanho correto da maior subsequência comum gerada pelo algoritmo para as entradas X={0,0,1,0,1,1,0,1} e Y={1,1,0,1,1,0,1,1,1,0,0}:

LCS-LENGTH(X, Y)
    m = X.length
    n = Y.length
    let c [0..m, 0..n] be new arrays
    for i = 0 to m
       c[i, 0] = 0
    for j = 0 to n
       c[0, j] = 0
    for i = 1 to m
        for j = 1 to n
            if X[i] = Y[j]
                c[i, j] = c[i - 1,j - 1] + 1
            else
                c[i, j] = MAX(c[i, j - 1], c[i - 1, j])
    return c[m, n

Auxiliado pelo algoritmo MAX(i, j)

MAX(i, j)
    if i >= j
        return i
    else
        return j

1. 4
2. 5
3. 6
4. 7
5. NDA 

Ideia original de: Luís Guilherme Cordiolli Russi