Programação das aulas de MAC6711
Primeiro semestre de 2018
Março
Abril
- 3 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].
- 6 de abril (Aula 8):
- Corte mínimo em um grafo
- Hashing
Leitura recomendada: Secs 13.2 e 13.6 do KT.
Slides [pdf].
- 10 de abril:
Matéria da prova: notação assintótica,
resolução de recorrência, divisão e conquista, algoritmos probabilísticos.
- 13 de abril (Aula 9):
- 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].
- 17 de abril (Aula 10):
- 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. E Sec 16.5?
Slides [pdf].
- 20 de abril (Aula 11):
- Caching ótimo e LRU
- Política aleatorizada de caching
Leitura recomendada: Secs 4.3 e 13.8 do KT.
Slides [pdf].
- 24 de abril (Aula 12):
- Clustering
- Relembrar Prim e Kruskal e sua implementação
Leitura recomendada: Sec 4.5, 4,6 e 4.7 do KT.
Slides [pdf].
- 27 de abril (Aula 13):
- Análise amortizada
- Tabelas dinâmicas
- Lista 5
Leitura recomendada: Cap 17 do CLRS.
Slides [pdf].
Maio