Programação das aulas de MAC6711

Abril

Maio

• 5 de maio (Aula 6):
  • Algoritmos probabilísticos
    
  • Teste de igualdade de polinômios
  • Problema da contenção
  • Comentários sobre o algoritmo do exponential backoff time
  Leitura recomendada: Sec 1.1 do livro Probability and Computing: Randomized Algorithms and Probabilistic Analysis, de Computing and Probability (QA274.M574 2005), e começo do Cap 13 e Sec 13.1 e 13.2 do KT. Leia também a explicação sobre o algoritmo de exponential backoff time, que é utilizado na Ethernet.
  Slides [pdf].

• 7 de maio (Aula 7):
  • Quicksort e Select aleatorizados
  • Par mais próximo de pontos: um algoritmo aleatorizado
  • Lista 3
  Leitura recomendada: Secs 7.3, 7.4 e 9.2 do CLRS. Sec 13.7 do KT.
  Slides [pdf].

• 12 de maio (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].

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

• 19 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].

• 21 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].

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

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