jho

MO417 - Questão para a prova oral

Número: 

Enunciado: Considere as seguintes afirmações: 
  
  (I)  É possível obter todas as LCS de dois sequências X e Y a partir da matriz de distâncias "c", retornada pelo algoritmo LCS-LENGTH(X, Y).

 (II)  O seguinte algoritmo imprime corretamente uma LCS de dois secuencias X e Y, em O(X.lentgh+Y.length), a partir de a matriz de distâncias "c"  devolvido pelo algoritmo LCS-LENGTH(X, Y):

                            PRINT_LCS( c, X, Y, i, j)

                            1   if  i == 0 or j == 0

                            2       return 

                            3   if  Xi == Yj

                            4       PRINTF_LCS(c, X, Y, i-1, j-1)

                            5       print Xi

                            6   else if  c[i-1][j] ≥ c[i][j-1]

                            7       PRINTF_LCS(c, X, Y, i-1, j) 

                            8   else PRINTF_LCS(c, X, Y, i, j-1)

A primeira chamada do algoritmo é: PRINT_LCS( c, X, Y, X.length, Y.length)

 (III)  O seguinte algoritmo imprime corretamente uma LCS de dois secuencias X e Y, em O(X.lentgh+Y.length), a partir de a matriz de distâncias "c"  devolvido pelo algoritmo LCS-LENGTH(X, Y), em O(X.lentgh+Y.length):

                            PRINT_LCS( c, X, Y, i, j)

                            1   if  i == 0 or j == 0

                            2       return 

                            3   if  Xi == Yj

                            4       PRINTF_LCS(c, X, Y, i-1, j-1)

                            5       print Yj

                            6   else if  c[i-1][j]  <  c[i][j-1]

                            7       PRINTF_LCS(c, X, Y, i, j-1) 

                            8   else PRINTF_LCS(c, X, Y, i-1, j)

A primeira chamada do algoritmo é: PRINT_LCS( c, X, Y, X.length, Y.length)

Assinale a alternatica correta:

1. Somente (I) é verdadeira.
2. Somente (III) é verdadeira.
3. (I) e (II) são verdadeiras.
4. Todas são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga