Programação das aulas de MAC6711
Primeiro semestre de 2018
Março
Abril
Maio
- 1 de maio (Dia do Trabalho) - Não há aula
- 4 de maio (não haverá aula) - segunda semana de break
- 8 de maio (Aula 14):
- Heuristica MTF (move to front)
- Splay trees
Leitura recomendada: Amortized Analysis Explained
Slides [pdf].
- 11 de maio (aula 15):
- Splay trees - continuação (inserção e fim da análise)
Leitura recomendada: Amortized Analysis Explained e Splay Trees - Lecture Notes (fala da inserção).
Slides [pdf].
- 15 de maio (aula 16):
- Union-find: análise amortizada
Leitura recomendada: Secs 21.3 e 21.4 do
CLRS e notas de aula [pdf].
Slides [pdf].
- 18 de maio (aula 17):
- Busca de padrão
- Algoritmo de Boyer-Moore
- Simulações do BM
- Busca de padrão: Algoritmo KMP; Sec 32.4 do CLRS.
Leitura recomendada: Cap 13 do livro Algoritmos,
do Prof. Paulo. (Veja as notas de aulas correspondentes na página dele.)
Slides [pdf].
- 22 de maio:
Matéria da prova: algoritmos probabilísticos, gulosos, e análise amortizada.
- 25 de maio (aula 18):
- Algoritmo para casamento estável
- Lista 6
Leitura recomendada: Sec 1.1 do KT. Por curiosidade, leia também essa página da wiki.
Slides [pdf].
- 28 de maio a 1 de junho: terceira semana de break (não há aula)
Junho