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
Maio e junho
- 5 de maio (aula 16)
- Análise amortizada.
- Exemplo 2: pilha com operações POP, PUSH e MULTIPOP.
- Estrutura de dados para conjuntos disjuntos (union-find):
implementação usando listas ligadas.
Leitura recomendada: CLR, cap 18.
- 8 de maio (aula 17)
- Estrutura de dados para conjuntos disjuntos (union-find):
implementação usando florestas disjuntas.
Leitura recomendada: CLR, cap 22.
- 12 de maio
Matéria da prova: limite inferior para ordenação e problemas
semelhantes, algoritmos lineares para ordenação, k-ésimo mínimo,
medianas, programação dinâmica e análise amortizada. (Capítulos
9, 10, 16 e 18 do CLR; olhe aqui para
saber os capítulos correspondentes no CLRS).
- 15 de maio
- Algoritmos gulosos: problema da coleção máxima de
intervalos disjuntos.
[ps]
[pdf]
Leitura recomendada: CLR, cap 17.
- 19 de maio
- Problema da mochila.
[ps]
[pdf]
- 22 de maio
- Algoritmo de Kruskal.
- Códigos de Huffman.
- 2 de junho
- Busca de padrão: algoritmo ingênuo e KMP.
Leitura recomendada: CLR, sec 34.1 e 34.4
- 5 de junho
- Tabelas de espalhamento (hashing).
Leitura recomendada: CLR, cap 12.
- 9 de junho
- Tabelas de espalhamento (hashing).
- Complexidade computacional.
Leitura recomendada: CLR, sec 36.1 e 36.2.
- 12 de junho
- 16 de junho
- Complexidade computacional.
- 23 de junho
Matéria da prova: union-find, algoritmos gulosos, busca de
padrão, hashing e complexidade computacional.
Last modified: Thu Jun 19 14:13:08 EST 2003