Lista de exercicio 9 Analise e Projeto de Algoritmos

Aluno: Vinícius Barcelos Silva
Matricula: 108251
Lista 9 15.1­4
Podemos notar que mesmo existindo 4n­2 entradas, teoricamente apenas a metade está sendo usada, pois o caminho mais rápido que é o que nos interessa, pode ser obtido com a metade do número de entradas.
Nós perderíamos um pouco de desempenho, porém ganharíamos em espaço. Se percorrermos mais n vezes, poderemos guardar 2n+2 entradas, logo diminuiríamos o espaço e aumentamos um pouco o tempo. 15.1­5
Queremos mostrar que l 1[j] = 2 e l 2[j] = 1 é impossivel para qualquer j execução do FASTEST­WAY.
Devemos considerar para este caso os valores de f. Temos por definição que: f 1[j] = min(f 1[j − 1] + a 1,j, f 1[j − 1] + t 2,j−1 + a 1,j f 2[j] = min(f 2[j − 1] + a 2,j, f 2[j − 1] + t 1,j−1 + a 2,j
Desde que l 1[j] = 2 e l 2[j] = 1 temos que mostrar que: f 1[j − 1] + a 1,j > f 2[j − 1] + t 2,j−1 + a 1,j f 2[j − 1] + a 2,j > f 1[j − 1] + t 1,j−1 + a 2,j Cancelando os a’s teremos a contradição. 15.2­2
MATRIX­CHAIN­MULTIPLY(A, s, i, j)
1. if(i = j)
2.
then empilha(A)
3. else
4.
MATRIX­MULTIPLY(toppilha(A))
5.
MATRIX­CHAIN­MULTIPLY(A, s, i, s[i, j])
6.
MATRIX­CHAIN­MULTIPLY(A, s, s[i, j] + 1, j)
7.
MATRIX­MULTIPLY(desimpilha(A))

15.3­1
RECURSIVE­MATRIX­CHAIN é assintoticamente mais eficiente que a enumeração. Temos muito mais possiveis combinações na enumeração. Assim o tempo de cada uma é: n−1 RECURSIVE­MATRIX­CHAIN:
Enumeração:

O(n 3 )

Ω(4n /n3/2 )

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 memoização não vai melhorar o tempo de execução. 15.3­3

Sim, a maximização de parenteses possui subestrutura otima, como foi estudado os subproblemas são independentes e possuem a mesma caracteristica de resolução inclusive com o problema como um todo. 15.4­4
Não precisamos usar uma matriz m*n uma vez que guardar