Programação das aulas de MAC6711

Março

Abril

• 2 de abril (Aula 8):
  • Corte mínimo em um grafo: algoritmo de Karger
  Leitura recomendada: Secs 13.2 do KT e entrada da wiki sobre o algoritmo de Karger. Lá você encontra a descrição da versão acelerada do algoritmo, proposta por Karger e Stein.
  Slides [pdf].

• 7 de abril (Aula 9):
  • Hashing
  Leitura recomendada: Secs 13.6 do KT.
  Slides [pdf].

• 9 de abril: Semana Santa (não há aula)

• 14 de abril (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].

• 16 de abril (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].

• 21 de abril: não haverá aula, Tiradentes.

• 23 de abril (Aula 12):
  • Caching ótimo
  • Algoritmo ótimo para caching
  Leitura recomendada: Sec 4.3 do KT.
  Slides [pdf].

• 28 de abril (Aula 13):
  • Caching: algoritmos de marcação, LRU
  • Política aleatorizada de caching
  Leitura recomendada: Sec 13.8 do KT.
  Slides [pdf].

• 30 de abril (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].