Programação das aulas de MAC0338
Primeiro semestre de 2016
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.
Fevereiro
Março
- 2 de março (aula 5):
- Análise probabilística
- Cálculo do máximo
- Análise do caso médio do Quicksort
- Lista 3
Slides: [pdf]
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.
- 4 de março (aula 6):
- Quicksort probabilístico
- Consumo de tempo esperado
- Select probabilístico
- Consumo de tempo esperado
Slides: [pdf]
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.
- 9 de março (aula 7)
- Cota inferior para ordenação
- Ordenação em tempo linear
- Lista 4
Slides. [pdf]
Leitura recomendada: CLRS Cap 8 Sorting in Linear Time.
- 11 de março (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.
- 16 de março (aula 9)
Slides. [pdf]
Leitura recomendada: CLRS Sec 9.3 Selection in worst-case linear time.
- 18 de março (aula 10)
Slides. [pdf]
Leitura recomendada: CLRS Cap 12 Hash tables.
- 21 e 25 de março: Semana Santa
- 30 de março
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.
Abril
Maio