Programação das aulas de MAC5711
Primeiro semestre de 2004
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)
- Remoção do máximo em um heap.
- Construção de um heap.
- Heapsort.
- Limite inferior para ordenação
[ps]
[dvi]
[html].
- Lista 3
- 6 de abril
- Aula de exercícios/plantão de dúvidas com o monitor.
- 13 de abril (aula 9)
Matéria da prova: notação assintótica, recorrências,
ordenação, divisão e conquista, Strassen, multiplicação de
números grandes. (Capítulos 1, 2, 4.1, 4.2, 7, 8 e 31 do CLR
e pgs 109-111 das notas de aula do David Mount.)
- 15 de abril (aula 10)
- Insertionsort com tempo esperado O(n log n).
- Ordenação em tempo linear: countingsort e radixsort.
- Desafio novo (mais fácil que o cript) na nossa classe do
PC (Programming Challenges)!
Exercício 1: Dadas duas seqüências, cada uma com n inteiros entre 1 e 5n,
determinar se as duas seqüências são iguais em tempo O(n). [Fácil]
Exercício 2: A mesma coisa, porém agora os números nas
seqüências são inteiros entre 1 e 2n. [Se você resolver o
desafio proposto na aula de hoje, você resolve este exercício.]
Leitura recomendada: CLR, cap 9.
- 20 de abril (aula 11)
- Problema do k-ésimo mínimo.
- Comparação experimental entre os vários algoritmos de ordenação
[txt].
- Lista 4.
Leitura recomendada: CLR, cap 10.
- 22 de abril (aula 12)
- Problema do k-ésimo mínimo - continuação
[ps.gz][pdf].
- Veja uma implementação do algoritmo linear para o
k-ésimo mínimo aqui.
- Exercício: Dê uma recorrência que define o número pedido no problema
Counting (110603) do
Programming Challenges.
- 27 de abril (aula 13)
- Solução do desafio de evitar a inicialização de um vetor sem incorrer
em custo adicional de tempo (porém com custo adicional de espaço).
- Programação dinâmica [ps.gz]
[pdf].
- Recorrência do problema Counting (110603) do
Programming Challenges
e discussão sobre como calculá-la.
- Recorrência para contar o número de seqüências bem-formadas de n pares
de parêntesis e profundidade no máximo e como calculá-la:
Solução 0: recursiva simples (ruim; não usa PD)
Solução 1: bottom-up
solução 2: top-down (recursiva com memoização)
solução 3: econômica
- 29 de abril (aula 14)
- Árvore de Busca Binária Ótima.
- Lista 5.
Leitura recomendada: CLRS, capítulo 15 (cap. 16 do CLR).
Maio
- 4 de maio (aula 15)
- Algoritmo de Floyd (sec. 26.2 do CLR; sec. 25.2 do CLRS).
- Triangularização ótima de polígonos (sec. 16.4 do CLR; não tem no CLRS).
- Problema da mochila.
- Dois desafios novos na nossa classe do
PC (Programming Challenges)!
- 6 de maio (aula 16)
- Alocação de atividades: programação dinâmica x método guloso.
- Versão fracionária do problema da mochila
[ps.gz]
[pdf].
- 11 de maio (aula 17)
- 13 de maio (aula 18)
- 18 de maio
Matéria da prova: ordenação em tempo linear, medianas e
k-ésimo mínimo, programação dinâmica e método guloso.
Além das notas de aula disponíveis...
Do CLRS, capítulos 8, 9, 15 e 16 e sec. 25.2 (+ sec. 16.4 do CLR);
Do CLR, capítulos 9, 10, 16 e 17 e sec. 26.2 (+ sec. 15.5 do CLRS);
Junho
Last modified: Tue Jun 1 13:21:03 BRT 2004