Programação das aulas de MAC5711
Segundo semestre de 2019
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)
- Correção e aplicações de BFS.
- Algoritmos elementares para grafos: DFS
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.2 e 22.3.
- 4 de outubro (aula 15)
- Algoritmos elementares para grafos: DFS
- Ordenação topológica usando DFS
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.3 e 22.4.
- 6 e 12 de outubro: Segunda semana de break
- 15 de outubro
Matéria da prova: ordenação em tempo linear, cota inferior para ordenação, programação dinâmica, BFS e DFS.
- 18 de outubro (aula 16)
- Aplicação de DFS: Algoritmo Kosaraju-Shamir
Slides: [pdf]
Referências bibliográficas: CLRS sec 22.5.
- 22 de outubro (aula 17)
- Caminhos mínimos: algoritmo de Dijkstra
- Caminhos mínimos: algoritmo de Floyd-Warshall
- Lista 8
Slides: [pdf]
Leitura recomendada: CLRS cap 25 até a sec 25.2 e sec 26.2.
- 25 de outubro (aula 18)
- Árvores geradoras mínimas: algoritmo de Prim
- Árvores geradoras mínimas: algoritmo de Kruskal
- Union-Find
Slides: [pdf]
Leitura recomendada: CLRS cap 23 e cap 21.
- 29 de outubro (aula 19)
- Complexidade computacional
Slides: [pdf]
Leitura recomendada: notas de aula e CLRS cap 34.
Novembro