Programação das aulas de MAC338
Primeiro semestre de 2005
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).
Março
Abril
- 1 de abril (aula 8)
- Quicksort - comentários sobre o pior e melhor caso.
- Algoritmos probabilísticos.
- Versões probabilísticas do quicksort.
Transparências. [pdf] [ps.gz]
Referências bibliográficas: CLRS cap 7.
- 6 de abril (aula 9)
- Recorrências - um pouco sobre como chegar ao chute.
- Seleção do i-ésimo mínimo.
Transparências. [pdf] [ps.gz]
Referências bibliográficas: CLRS cap 9.
- 8 de abril
Matéria da prova: notação assintótica,
resolução de recorrências, algoritmos recursivos, divisão e conquista,
análise de caso médio, ordenação.
- 13 de abril (aula 10)
- Comentários da prova.
- Revisão da análise de caso médio do algoritmo visto
na aula passada para o i-ésimo mínimo.
Transparências. [pdf] [ps.gz]
Referências bibliográficas: CLRS cap 9.
- 15 de abril (aula 11)
- Seleção do i-ésimo mínimo em tempo linear.
- Um par de exercícios probabilísticos... [pdf] [ps.gz]
- Lista 4 [pdf] [ps.gz]
Transparências. [pdf] [ps.gz]
Referências bibliográficas: CLRS sec 9.3.
- 27 de abril (aula 12)
- Delimitação inferior para ordenação.
- Ordenação em tempo linear.
- 29 de abril (aula 13)
- Radixsort.
- Um ou dois exercícios para ajudar na nota da P1. Não falte!
- 4 de maio (aula 14)
- Programação dinâmica: parentisação ótima.
Transparências. [pdf] [ps.gz]
Referências bibliográficas: CLRS sec 15.1 a 15.3.
- 6 de maio (aula 15)
- Programação dinâmica: subseqüência comum máxima.
Transparências. [pdf] [ps.gz]
- 11 de maio (aula 16)
- Programação dinâmica: árvore de busca binária ótima.
- Número de aparições de Z em X.
- Lista 5 [pdf] [ps.gz].
- 13 de maio
- Programação dinâmica: mochila (knapsack).
- Lista 6 [pdf] [ps.gz].
Transparências. [pdf] [ps.gz]
- 18 de maio
- Aula de exercício.
- Aula de exercício das 12 às 13 na sala 9-B com o monitor!
- 20 de maio
Matéria da prova: seleção do k-ésimo
mínimo, delimitação inferior para ordenação, algoritmos lineares
de ordenação, countingsort, radixsort, etc, programação
dinâmica.
Junho
Last modified: Tue May 31 11:42:33 BRT 2005