As transparências se baseiam nas feitas pelos Profs. Paulo Feofiloff, José Coelho de Pina e Cristina Gomes Fernandes.

Referências

• CLRS é Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms, 3a edição.
• KT é Kleinberg e Tardos, Algorithm Design.

1. 8/08 - Aula 1 (Transparências/Papel)(o que teria sido mostrado se o computador tivesse funcionado)
   • Como contar instruções
   • Por que ignorar as constantes
   • Notação O
   Leitura recomendada: CLRS, secs 1.1 Algorithms, 1.2 Algorithms as a technology, 2.1 Insertion sort e 2.2 Analyzing algorithms.
2. 10/08 - Aula 2 (Transparências/Papel)
   • Notação assintótica: O, Ω e Θ
   • Crescimento de funções
   • Análise de pior caso, melhor caso e caso médio do InsertionSort
   Leitura recomendada: CLRS, sec 3.1 Asymptotic notation e 3.2 Standard notation and common functions. Se tiver dificuldades com a parte matemática, revise o material coberto nos apêndices A Summations e parte do C Counting and probability do CLRS.
3. 15/08 - Aula 3 (Transparências/Papel)
   • Mergesort
   • Recorrências
   Leitura recomendada:sec 2.3 Designing algorithms e começo do cap 4 Recurrences, incluindo a sec 4.1 The substitution method. Veja também Solving Recurrences, do Jeff Erickson.
4. 17/08 - Aula 4 (Transparências/Papel)
   • Quicksort
   • Análises de pior e melhor caso
   • Um pouco mais sobre recorrências, incluindo como lidar com arredondamentos.
   Leitura recomendada:sec 4.2 The recursion-tree method e parte do cap 7 Quicksort do CLRS até sec 7.2.
5. 22/08 - Aula 5 (Transparências/Papel)
   • Análise probabilística
   • Cálculo do máximo
   • Análise do caso médio do Quicksort
   Leitura recomendada: CLRS cap 7 Quicksort todo e CLRS secs 5.1 The hiring problem e 5.2 Indicator random variables, apêndices C.1 a C.3.
6. 24/08 - Aula 6 (Transparências/Papel)
   • Quicksort aleatorizado
   • Select aleatorizado
   Leitura recomendada: CLRS secs 7.3 e 7.4 do capítulo Quicksort e secs 9.1 e 9.2 do capítulo Medians and Order Statistics. KT, sec 13.5.
7. 29/08 - Aula 7
   • Heapsort (Transparências)
   • Cota inferior para ordenação
   Leitura recomendada: CLRS sec 6, CLRS secs 4.3-4.6,8.1, KT 5.2
8. 12/09 - Aula 8 (Transparências/Papel)
   • Ordenação em tempo linear
   Leitura recomendada: CLRS cap 8
9. 14/9 - Aula 9 (Transparências/Papel)
   • Elementos de programação dinâmica
   • Ex: Números de Fibonacci
   • Ex: corte de hastes
   Leitura recomendada: CLRS cap 15
10. 21/9 - Aula 10 (Transparências/Papel)
    • Multiplicação de cadeias de matrizes
    • Elementos de programação dinâmica
    • Árvore binária de busca ótima
    Leitura recomendada: CLRS cap 15
11. 19/9 - Aula 11 (Transparências/Papel)
    • Subsequência comum máxima
    • Problema da mochila
    • Seam carving
    Leitura recomendada: CLRS cap 15
12. 28/9 - Aula 12 (Transparências/Papel)
    • Grafos e suas representações
    • Busca em largura
    Leitura recomendada: CLRS cap 22, secs 1,2
13. 3/10 - Aula 13 :-) ... Prova - Obaaaa!
14. 5/10 - Aula 14 (Transparências/Papel)
    • Busca em largura, prova de corretude
    • Aplicações: componentes conexas, reconhecimento de grafos bipartidos
    Leitura recomendada: CLRS cap 22, secs 1,2
15. 10/10 - Break
16. 17/10 - Aula 15 (Transparências/Papel)
    • Busca em profundidade, estrutura parentizada.
    • Aplicação: ordenação topológica.
    Leitura recomendada: CLRS cap 22, secs 3, 4.
17. 19/10 - Aula 16 (Transparências/Papel)
    • Relações de equivalência e componentes fortemente conexas
    • Algoritmo de Kosaraju-Sharir
    • Condensação de um digrafo
    Leitura recomendada: CLRS cap 22, secs 3, 4.
18. 24/10 - Aula 17 (Transparências/Papel)
    • Caminhos de comprimento mínimo
    • Algoritmo de Dijkstra
    • Algoritmo de Floyd-Warshall
    Leitura recomendada: CLRS secs 24.3 e 25.2
19. 26/10 - Aula 18 (Transparências/Papel)
    • Árvore geradora mínima
    • Algoritmo de Prim
    • Algoritmo de Kruskal
    • Necessidade do Union-Find
    Leitura recomendada: CLRS cap 23
20. 31/10 - Aula 19 (Transparências/Papel)
    • Union-Find
    Leitura recomendada: CLRS cap 21
21. 7/11 - Aula 20 (Transparências/Papel)
    • Complexidade algorítmica de problemas
    • A classe P
    • Certificados curtos e a classe NP
    • O problema P=NP
    Leitura recomendada: CLRS cap 34
22. 9/11 - Aula 21 (Transparências/Papel)
    • Redução polinomial de problemas
    • Algumas reduções
    • Teorema de Cook-Levin
    Leitura recomendada: CLRS cap 34
23. 21/11 - Aula 22 (Transparências/Papel)
    • Redução polinomial de problemas
    • Provas de NP-completude via reduções
    • Problemas NP-difíceis
    Leitura recomendada: CLRS cap 34