Programação das aulas de MAC6711
Primeiro semestre de 2014
Fevereiro e Março
Abril
Maio
- 2 de maio (recesso escolar) - Não há aula
- 6 de maio (Aula 14):
- Heuristica MTF (move to front)
- Splay trees
- Lista 5 - a ser disponibilizada em breve
Leitura recomendada: Amortized Analysis Explained e Splay Trees - Lecture Notes (fala da inserção).
Transparências [pdf].
- 9 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].
- 13 de maio (aula 16):
- Busca de padrão
- Algoritmo de Boyer-Moore
Leitura recomendada: Cap 13 do livro Algoritmos,
do Prof. Paulo. (Veja as notas de aulas correspondentes na
página dele.)
Transparências [pdf].
- 16 de maio (aula 17):
- Simulações do BM
- Busca de padrão: Algoritmo KMP
Leitura recomendada: Sec 32.4 do CLRS.
Transparências [pdf].
- 20 de maio:
Matéria da prova:
algoritmos gulosos e análise amortizada.
- 23 de maio (aula 18):
- Comentários sobre a prova
- Algoritmo para casamento estável
- Lista 6
Leitura recomendada: Sec 1.1 do KT.
Transparências [pdf].
- 27 de maio (aula 19):
- 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].
- 30 de maio (aula 20):
- Algoritmos de aproximação
- Problema do caixeiro viajante
- Problema da cobertura por conjuntos
Leitura recomendada: Sec 11.3 e 11.6 do KT.
Transparências [pdf]
Junho