Lista de exercicio 8 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinícius Barcelos Silva 
Matricula: 108251 
 
 
15.1­5 
Queremos mostrar que   é impossivel para qualquer j execução do FASTEST­WAY.  [j]  e l  [j]  l 1 = 2 2 = 1  
Devemos considerar para este caso os valores de f. Temos por definição que: 
  [j] in(f   [j ]   , f   [j ]    f 1 = m 1 −1 + a 1,j   1 −1 + t 2,j−1+ a 1,j  
  [j] in(f   [j ]   , f   [j ]    f 2 = m 2 −1 + a 2,j   2 −1 + t 1,j−1+ a 2,j  
Desde que  temos que mostrar que:  [j]  e l  [j]  l 1 = 2 2 = 1  
  [j ]     f   [j ]    f 1 −1 + a 1,j >   2 −1 + t 2,j−1+ a 1,j  
  [j ]     f   [j ]    f 2 −1 + a 2,j >   1 −1 + t 1,j−1+ a 2,j  
 
Cancelando os a’s teremos a contradição. 
 
15.3­2 
O Mergesort executa no máximo uma única chamada para qualquer par de índices da matriz que está 
sendo analisada. Os subproblemas não se sobrepõem, logo a memorização não vai melhorar o tempo de 
execução. 
 
15.4­4 
Ao calcular uma linha específica da tabela de c, nenhuma linha antes da linha anterior é necessária. 
Assim, apenas duas linas (2xlength[Y]) Precisam ser mantidos na memória de cada vez. 
Com esta idéia, precisamos de apenas 2 ∙ min (m, n) entradas se sempre 
chamar LCS­LENGTH com a seqüência mais curta como o argumento Y. 
Podemos, assim, acabar com o quadro de c da seguinte forma: 
 
• Use duas matrizes de comprimento min (m, n), previous­row e current­row, para manter a 
linhas apropriadas de c. 
• Inicializar previous­row com 0 e calcular current­row da esquerda para a direita. 
• Quando a current­row é prrenchida, se ainda existem mais linhas para calcular, cópia 
current­row na previous­row e calcular a nova current­row 
 
15.4­5 
Devemos classificar os elementos de X e criar uma outra sequência . Depois encontrar a sub sequênciaX  0  
comum mais longa de X e   e produzir a maior sub sequência monotônica de X. O funcionamento dela éX  0  
de ordem , sua triagem é feita geralmente em tempo   e a chamada do LCS­LENGHT é  .)O(n2 (n lg n)O )O(n2