Programação das aulas de MAC6711
Primeiro semestre de 2015
Março
Abril
Maio
- 1 de maio (Dia do Trabalho) - Não há aula
- 6 de maio (Aula 12):
- Análise amortizada
- Tabelas dinâmicas
Leitura recomendada: Cap 17 do CLRS.
Transparências [pdf].
- 8 de maio (Aula 13):
- Heuristica MTF (move to front)
- Splay trees
- Lista 5
Leitura recomendada: Amortized Analysis Explained e Splay Trees - Lecture Notes (fala da inserção).
Transparências [pdf].
- 13 de maio (Aula 14):
- Clustering
- Relembrar Prim e Kruskal e sua implementação
Leitura recomendada: Sec 4.5, 4,6 e 4.7 do KT.
Transparências [pdf].
- 15 de maio:
Matéria da prova: algoritmos probabilísticos, gulosos, e análise amortizada.
- 20 de maio (aula 15):
- Union-find: análise amortizada
Leitura recomendada: Secs 21.3 e 21.4 do
CLRS e notas de aula [pdf].
Transparências [pdf].
- 22 de maio (aula 16):
- Busca de padrão
- Algoritmo de Boyer-Moore
- Simulações do BM
Leitura recomendada: Cap 13 do livro Algoritmos,
do Prof. Paulo. (Veja as notas de aulas correspondentes na página dele.)
Transparências [pdf].
- 27 de maio (aula 17):
- Algoritmo para casamento estável
- Lista 6
Leitura recomendada: Sec 1.1 do KT. Por curiosidade, leia também essa página da wiki.
Transparências [pdf].
- 29 de maio (aula 18):
- Algoritmos de aproximação
- Escalonamento: algoritmo de Graham
- Problema dos k-centros: 2-aproximação
Leitura recomendada: Sec 11.1 e 11.2 do KT.
Transparências [pdf].
Junho