Programação das aulas de MAC338
Primeiro semestre de 2003
CLR refere-se à primeira edição do livro do Cormen, Leiserson e Rivest.
Há uma diferença na numeração em relação à edição mais nova, que tem
alguns capítulos a mais.
Olhe aqui para
uma correspondência da numeração da primeira para a segunda edição, em que o
livro ganhou mais um autor (CLRS, de Cormen, Leiserson, Rivest e Stein).
Fevereiro
- 17 de fevereiro (aula 1):
- Introdução.
- Qual das duas funções você prefere?
[f1][f2]
Pense, decida e depois execute cada uma para algumas
entradas. Escolha como entrada números entre 10 e
20. Aumente gradativamente se não der para sentir a
diferença entre as duas e decida se a sua escolha foi
boa.
- Ordenação - método de inserção.
Leitura recomendada: CLR, sec 1.1 e 1.2.
- 20 de fevereiro (aula 2):
- Notação assintótica.
- Chute a complexidade do algoritmo!
[ps.gz][pdf]
Leitura recomendada: CLR, cap 2 e 3.
Exrcícios recomendados: 2-1 e 2-4 do CLR.
- 24 de fevereiro (aula 3)
- Notação assintótica em equações.
- Divisão e conquista
- Mergesort
- Resolução de recorrências.
Exercícios: 4.2-2 e 4.2-3 do CLR.
Leitura recomendada: CLR, sec 1.3, 1.4, 4.1 e 4.2.
- 27 de fevereiro (aula 4)
- Um pouco mais sobre recorrências.
- Quicksort - análise do pior caso.
Leitura recomendada: CLR, cap 8.
- 10 de março (aula 5)
- Versões probabilísticas do quicksort.
- Análise do caso médio de uma das versões probabilísticas do quicksort.
- Discussão sobre análise de caso médio.
Veja notas de aula. [ps]
[pdf]
- 13 de março (aula 6)
- Lista 2.
- Seleção.
- Limite inferior para o cálculo do máximo (ou mínimo).
- Heaps.
- 17 de março (aula 7)
- Remoção do máximo em um heap.
- Construção de um heap.
- Heapsort.
Leitura recomendada: CLR, sec 7.1, 7.2, 7.3 e 7.4.
- 20 de março (aula 8)
- Comparação experimental entre os vários algoritmos de ordenação
[txt].
- Aula de exercícios.
- Simulado 1 [ps.gz]
[pdf].
- 24 de março
Matéria da prova: notação assintótica, recorrências, ordenação
(capítulos 1, 2.1, 4.1, 4.2, 7, 8 do CLR).
- 27 de março (aula 9)
- Limite inferior para ordenação
[ps.gz]
[html].
- Algoritmos lineares de ordenação.
- Lista 4.
Leitura recomendada: CLR, cap 9.
- 31 de março (aula 10)
- Radixsort.
- Problema do k-ésimo mínimo
[ps.gz][pdf].
Leitura recomendada: CLR, cap. 10.
Abril
Maio e junho
Last modified: Mon Jun 9 12:09:11 EST 2003