Programação das aulas de MAC6711

Março

Abril

Maio

• 2 de maio (Aula 10):
  • Método guloso
  • Escalonamento de tarefas (coleção máxima de intervalos disjuntos)
  • Alocação de salas de aula
  Leitura recomendada: Sec 4.1 do KT e 16.1 do CLRS.
  Slides [pdf].

• 5 de maio (Aula 11):
  • Escalonamento com atraso máximo mínimo
  • Um pouco sobre matroides
  • Lista 4
  Leitura recomendada: Sec 4.2 do KT e Sec 16.4 do CLRS.
  Slides [pdf].

• 9 de maio (Aula 12):
  • Caching ótimo
  • Algoritmo ótimo para caching
  • Algoritmos de marcação
  Leitura recomendada: Sec 4.3 do KT.
  Slides [pdf].

• 12 de maio (Aula 13):
  • Caching: algoritmos de marcação, LRU
  • Política aleatorizada de caching
  • Exercício 12 da L3 e Exercício 10 da L4
  Leitura recomendada: Sec 13.8 do KT.
  Slides [pdf].

• 16 de maio (Aula 14):
  • Clustering
  • Relembrar Kruskal e sua implementação
  • Lista 5
  Leitura recomendada: Sec 4.5, 4.6 e 4.7 do KT.
  Slides [pdf].

• 19 de maio (Aula 15):
  • Análise amortizada
  • Tabelas dinâmicas
  Leitura recomendada: Cap 17 do CLRS.
  Slides [pdf].

• 23 de maio (Aula 16):
  • Tabelas dinâmicas - análise por potencial
  • Heuristica MTF (move to front)
  • Splay trees
  • Lista 6
  Leitura recomendada: Amortized Analysis Explained
  Slides [pdf].

• 26 de maio (Aula 17):
  • Análise amortizada: splay trees
  Leitura recomendada: Amortized Analysis Explained e Splay Trees - Lecture Notes (fala da inserção). Secs 1 a 3 das seguintes notas de aula.
  Slides [pdf].

• 30 de maio:
  • Não haverá aula (a P2 foi adiada para 6/6).