Programação das aulas de MAC0338
Segundo semestre de 2017
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
- 1 de setembro (aula 8)
- Divisão e conquista: Karatsuba e Strassen
Slides: [pdf]
Leitura recomendada: KT Sec 5.5 Integer Multiplication e CLRS Sec 28.2 Strassen's algorithm for matrix multiplication.
Veja também a implementação deste algoritmo e outros na
GNU Multiple Precision Arithmetic Library.
- 3 e 9 de setembro: Semana da Pátria
- 12 de setembro (aula 9)
Slides: [pdf]
Leitura recomendada: CLRS Sec 9.3 Selection in worst-case linear time.
- 15 de setembro
Matéria da prova: notação assintótica,
recorrências, análise de pior caso, de melhor caso, de caso médio,
ordenação, análise probabilística, divisão e conquista.
- 19 de setembro (aula 10)
- Programação dinâmica: introdução
- Corte de hastes
- Lista 5
Slides: [pdf]
Leitura recomendada: CLRS Sec 15.1 Dynamic Programming.
- 22 de setembro (aula 11)
- Programação dinâmica
- Produto de cadeias de matrizes
- Subsequência comum mais longa - discussão inicial
Slides: [pdf]
Leitura recomendada: CLRS secs 15.2 a 15.3.
- 26 de setembro (aula 12)
- Programação dinâmica
- Subsequência comum mais longa
- ABB ótima
Slides: [pdf]
Leitura recomendada: CLRS Secs 15.4 e 15.5.
- 29 de setembro (aula 13):
- Programação dinâmica
- Problema da mochila
Slides: [pdf]
Leitura recomendada: KT 6.4.
Outubro
Novembro
Dezembro