Programação das aulas de MAC5711
Primeiro semestre de 2022
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.
Março
Abril
- 1 de abril (aula 4):
- Quicksort
- Análises de pior e melhor caso
- Lista 2
Slides: [pdf]
Leitura recomendada: sec 4.4 The recursion-tree method e parte do cap 7 Quicksort do CLRS até sec 7.2.
Mais sobre notação assintótica e recorrências num excelente texto de AA do Professor Paulo Feofiloff [pdf].
- 6 de abril (aula 5):
- Análise probabilística
- Cálculo do máximo
- Análise do caso médio do Quicksort
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.
- 8 de abril (aula 6):
- Quicksort probabilístico
- Consumo de tempo esperado
- Select probabilístico
- Consumo de tempo esperado
- Lista 3
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.
- 11 a 15 de abril (Semana Santa) - não há aula
- 20 de abril (aula 7):
- Filas de prioridade (heaps)
- Heapsort
- Cota inferior para ordenação
- Lista 4
Slides: [pdf]
Leitura recomendada: CLRS Cap 6 Heapsort e Sec 8.1.
- 22 de abril: recesso (Tiradentes)
- 27 de abril (aula 8)
- Ordenação em tempo linear
- Análise probabilística do Bucketsort
- Dicas sobre algoritmos de ordenação.
- Lista 5
Slides. [pdf]
Leitura recomendada: CLRS Secs 8.2, 8.3 e 8.4 Sorting in Linear Time e SW cap 2.
- 29 de abril
Matéria da prova: notação assintótica, divisão e conquista, recorrências, análise de pior caso, de melhor caso, de caso médio, ordenação, seleção de k-ésimo, cota inferior para ordenação.
Maio