Programação das aulas de MAC6711

Março

Abril

Maio

• 1 e 3 de maio (segunda semana de break)

• 8 de maio (Aula 14):
  • Caching ótimo e LRU
  • Política aleatorizada de caching
  Leitura recomendada: Secs 4.3 e 13.8 do KT.
  Transparências [pdf] [ps.gz].

• 10 de maio:
  • Segunda prova
  Matéria da prova: algoritmos probabilísticos e algoritmos gulosos.

• 15 de maio (aula 15):
  • Clustering
  • Relembrar Prim e Kruskal e sua implementação
  Leitura recomendada: Sec 4.5, 4,6 e 4.7 do KT.
  Transparências [pdf] [ps.gz].

• 17 de maio (aula 16):
  • Análise amortizada
  • Tabelas dinâmicas
  Leitura recomendada: Cap 17 do CLRS.
  Transparências [pdf] [ps.gz].

• 22 de maio (aula 17):
  • 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] [ps.gz].

• 24 de maio (aula 18):
  • Union-find: análise amortizada
  Leitura recomendada: Secs 21.3 e 21.4 do CLRS e notas de aula [pdf] [ps.gz]
  Transparências [pdf] [ps.gz].

• 29 de maio (aula 19):
  • 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] [ps.gz].

• 31 de maio (aula 20):
  • Busca de padrão: Algoritmo KMP
  • Algoritmo para casamento estável
  • Lista 6
  Leitura recomendada: Sec 32.4 do CLRS 4 e Sec 1.1 do KT.
  Transparências [pdf] [ps.gz].