Programação das aulas de MAC0338
Segundo semestre de 2024
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
- 5 de novembro (aula 21)
- Análise amortizada
- Tabelas dinâmicas
Slides: [pdf]
Leitura recomendada: CLRS cap 21 até a sec 21.3.
- 7 de novembro (aula 22)
- Heurística MTF (move to front)
- Splay trees
- Lista 9
Slides: [pdf]
Amortized Analysis Explained e Splay Trees - Lecture Notes (fala da inserção).
Secs 1 a 3 das seguintes notas de aula.
- 12 de novembro (aula 23)
- Finalizar a análise das splay trees
- Union-find
- Hashing
Slides: [pdf]
Leitura recomendada: CLRS cap 21.
- 14 de novembro (aula 24)
Slides: [pdf]
Leitura recomendada: estas notas e CLRS cap 34 até a sec 34.3.
- 19 de novembro (aula 25)
- Complexidade computacional
Slides: [pdf]
Leitura recomendada: CLRS cap 34.
- 21 de novembro (aula 26)
- Complexidade computacional
Slides: [pdf]
Leitura recomendada: CLRS cap 34.
- 26 de novembro
Matéria da prova: algoritmos em grafos,
análise amortizada, complexidade computacional.