Programação das aulas de MAC0338
Segundo semestre de 2022
CLRS refere-se ao livro de Cormen, Leiserson, Rivest e Stein,
Introduction to Algorithms, 3a edição
(cuidado que as seções mudam de uma edição para a outra),
SW refere-se ao livro de Sedgewick e Wayne, Algorithms, e
KT refere-se ao livro de Kleinberg e Tardos, Algorithm Design.
Agosto
Setembro
Outubro
Novembro
- 2 de novembro: Finados (não haverá aula)
- 4 de novembro (aula 17)
- Escalonamento com atraso mínimo
- Matroides e o método guloso
Slides: [pdf]
Leitura recomendada: KT 4.2 e CLRS Sec 16.4.
- 9 de novembro: não haverá aula
- 11 de novembro
Matéria da prova: programação dinâmica e algoritmos gulosos.
- 16 de novembro (aula 18)
- Árvores geradoras mínimas: algoritmo de Kruskal
- Árvores geradoras mínimas: algoritmo de Prim
- Lista 7
Slides: [pdf]
Leitura recomendada: CLRS Cap 23.
- 18 de novembro (aula 19)
- Caminhos mínimos: algoritmos de Dijkstra
- Caminhos mínimos: algoritmos de Floyd-Warshall (PD)
- Lista 8
Slides: [pdf]
Leitura recomendada: CLRS Sec 24.3 e Cap 25 até Sec 25.2.
- 23 de novembro (aula 20)
- Análise amortizada: introdução
- Tabelas dinâmicas
Slides: [pdf]
Leitura recomendada: CLRS 17.
- 25 de novembro (aula 21)
- Heurística MTF (move to front)
- Splay trees
Slides: [pdf]
Leitura recomendada:
Amortized Analysis Explained e Splay Trees - Lecture Notes (fala da inserção).
Secs 1 a 3 das seguintes notas de aula.
- 30 de novembro (aula 22)
- Splay trees: continuação
- Comentários sobre a P2
- Lista 9
Slides: [pdf]
Leitura recomendada: CLRS cap 21 até a sec 21.3.
Dezembro