Programação das aulas de MAC5711
Segundo semestre de 2005
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 e seções 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).
Para o índice da segunda edição, olhe aqui.
Agosto
Setembro
- 2 de setembro (aula 8)
- Selection
- Filas de prioridade
Leitura recomendada: CLRS, cap 6.
- 13 de setembro
Matéria da prova: notação assintótica,
resolução de recorrências, algoritmos recursivos, divisão e conquista,
análise de caso médio (análise probabilística), ordenação.
- 15 de setembro (aula 9)
Leitura recomendada: CLRS, cap 6 e sec 8.1.
Transparências [pdf]
[ps.gz].
- 20 de setembro (aula 10)
- Algoritmos gulosos e aplicações de heaps...
- Códigos de Huffman
Leitura recomendada: CLRS, sec 16.3.
Se você não tem familiaridade com algoritmos gulosos, talvez
queira ler também as seções 16.1 e 16.2.
- 22 de setembro (aula 11)
- Mais algoritmos gulosos
- Árvores geradoras mínimas
Leitura recomendada: CLRS, cap 23.
- 27 de setembro (aula 12)
- Algoritmo de Kruskal
- Union-find: primeira idéia
- Análise amortizada
- Lista 5
Leitura recomendada: CLRS, sec 23.2 e secs 21.1 e 21.2.
- 29 de setembro (aula 13)
- Union-find: segunda idéia
- Análise amortizada - uma revisão
Leitura recomendada: CLRS, sec 21.3.
Se você nunca viu análise amortizada, talvez queira dar uma lida
pelo menos numas partes do cap 17.
Outubro
Last modified: Tue Oct 18 14:46:57 EDT 2005