Programação das aulas de MAC0338
Segundo semestre de 2024
CLRS refere-se ao livro de Cormen, Leiserson, Rivest e Stein,
Introduction to Algorithms, 3a edição
(cuidado que as seções mudam de uma edição para a outra),
SW refere-se ao livro de Sedgewick e Wayne, Algorithms, e
KT refere-se ao livro de Kleinberg e Tardos, Algorithm Design.
Agosto
Setembro
Outubro
- 1 de outubro (aula 14)
- Problema da mochila
- Algoritmos gulosos: só um comecinho...
Slides: [pdf]
Leitura recomendada: KT 6.4.
- 3 de outubro (aula 15)
- Problema da mochila: finalização
- Problema dos caramelos
- Algoritmos gulosos
- Coleção máxima de intervalos disjuntos
Slides: [pdf]
Leitura recomendada: CLRS Cap 16.1 e 16.2.
- 8 de outubro (aula 16)
- Algoritmos gulosos
- Mochila fracionária
- Código de Huffman
- Coloração de intervalos
- Lista 6
Slides: [pdf]
Leitura recomendada: CLRS Sec 16.3.
- 10 de outubro (aula 17):
- Árvores geradoras mínimas: algoritmo de Kruskal
- Árvores geradoras mínimas: algoritmo de Prim
- Lista 7
Slides: [pdf]
Leitura recomendada: CLRS Cap 23.
- 13 a 19 de outubro: Semana de break
- 22 de outubro
Matéria da prova: Karatsuba e Strassen, programação dinâmica e algoritmos gulosos.
- 24 de outubro (aula 18)
- Um problema de escalonamento
- Escalonamento com atraso mínimo
- Matroides e o método guloso
- Lista 7
Slides: [pdf]
Leitura recomendada: KT 4.2 e CLRS Sec 16.4.
- 29 de outubro (aula 19)
- Matroides e o método guloso
- Caminhos mínimos: algoritmos de Dijkstra
- Lista 8
Slides: [pdf]
Leitura recomendada: CLRS Sec 24.3 e Cap 25 até Sec 25.2.
- 31 de outubro (aula 20)
- Caminhos mínimos: algoritmos de Floyd-Warshall (PD)
- Análise amortizada: introdução
Slides: [pdf]
Leitura recomendada: CLRS 17.
Novembro