Programação das aulas de MAC0338
Segundo semestre de 2024
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
- 6 de agosto (aula 1):
- Introdução [pdf]
- Por que ignorar as constantes?
- Notação O (Oh grande)
- Lista 1
Slides: [pdf]
Leitura recomendada: CLRS, secs 1.1 Algorithms,
1.2 Algorithms as a technology, 2.1 Insertion sort e 2.2 Analyzing algorithms.
- 8 de agosto (aula 2):
- Notação assintótica
- Crescimento de funções
- Análise de pior caso, melhor caso e caso médio do InsertionSort
- Divisão e conquista: Mergesort, análise do Intercala
Slides: [pdf]
Leitura recomendada: CLRS, sec 3.1 Asymptotic notation e 3.2 Standard notation and common functions,
parte da sec 2.3 Designing algorithms.
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.
- 13 de agosto (aula 3):
Slides: [pdf]
Leitura recomendada: CLRS, sec 2.3 Designing algorithms e começo do cap 4 Recurrences, incluindo a sec 4.1 The substitution method.
- 15 de agosto (aula 4):
- Quicksort
- Análises de pior e melhor caso
- Análise probabilística
- Cálculo do máximo
Slides: [pdf]
Leitura recomendada: sec 4.2 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].
- 20 de agosto (aula 5):
- 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.
- 22 de agosto (aula 6):
- Quicksort probabilístico e seu consumo de tempo esperado
- Select probabilístico e seu consumo de tempo esperado
- Cota inferior para ordenação
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.
- 27 de agosto (aula 7)
Slides: [pdf]
Leitura recomendada: CLRS Cap 8 Sorting in Linear Time.
- 29 de agosto (aula 8)
- Select em tempo linear
- Tempo para tirarem dúvidas para a prova
Slides: [pdf]
Leitura recomendada: CLRS Sec 9.3 Selection in worst-case linear time.
Setembro