Programação das aulas de MAC6711

Março

Abril

• 3 a 7 de abril: Semana Santa; não há aula

• 11 de abril (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 do KT. Leia também a explicação sobre o algoritmo de exponential backoff time, que é utilizado na Ethernet.
  Slides [pdf].

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

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

• 21 de abril: Tiradentes; não há aula

• 25 de abril:
  • Primeira prova
  Matéria da prova: divisão e conquista, e algoritmos probabilísticos; listas 1, 2 e 3.

• 28 de abril (Aula 9):
  • Comentários sobre a prova
  • Hashing
  Leitura recomendada: Secs 13.6 do KT.
  Slides [pdf].