Programação das aulas de MAC338
Primeiro semestre de 2003
CLR refere-se à primeira edição do livro do Cormen, Leiserson e Rivest.
Há uma diferença na numeração em relação à edição mais nova, que tem
alguns capítulos a mais.
Olhe aqui para
uma correspondência da numeração da primeira para a segunda edição, em que o
livro ganhou mais um autor (CLRS, de Cormen, Leiserson, Rivest e Stein).
Fevereiro e março
Abril
- 3 de abril (aula 11):
- Algoritmo linear para o problema do k-ésimo mínimo
[ps.gz][pdf].
Programa para testar o algoritmo linear para o problema do
k-ésimo mínimo [c].
Leitura recomendada: CLR, cap. 10.
- 7 de abril (aula 12)
- Programação dinâmica.
- Multiplicação de uma cadeia de matrizes.
Implementação não-recursiva [c].
Implementação recursiva, com memoização [c].
Leitura recomendada: CLR, sec 16.1.
- 10 de abril (aula 13)
- Programação dinâmica.
- Subseqüência comum mais longa.
Implementação não-recursiva [c].
Implementação recursiva, sem memoização [c].
Teste as duas implementações com o arquivo de entrada
disponível [txt]
(ou outro maior, se sua máquina for muito rápida) e sinta
a diferença no consumo do tempo. A segunda implementação
consome, como vimos, tempo exponecial em n, dependendo da
instância, enquanto que a outra consome tempo \Theta(nm).
Leitura recomendada: CLR, sec 16.2 e 16.3.
- 24 de abril (aula 14)
- Filas de prioridade.
- Programação dinâmica.
- Árvore de busca ótima.
Leitura recomendada: CLR, sec 7.5.
- 28 de abril (aula 15)
- Árvore de busca ótima.
- Análise amortizada: análise agregada e análise por créditos.
- Exemplo 1: contador binário
Leitura recomendada: cópia de dois livros que coloquei no xerox
sobre árvores de busca ótima e cap 18, sec 18.1 e 18.2 do CLR.
Maio e junho
Last modified: Mon Jun 9 12:09:21 EST 2003