Programação das aulas de MAC338
Primeiro semestre de 2013
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.
Fevereiro e Março
Abril
Maio
- 1 e 3 de maio: Segunda semana de break (Dia do trabalho; não haverá aula)
- 8 de maio (aula 16)
- Programação dinâmica: problema da mochila
Transparências.
[pdf] [ps.gz]
- 10 de maio (aula 17)
- Problema dos palitos chineses
- Método guloso: mochila fracionária
- Coleção máxima de intervalos disjuntos
Referências bibliográficas: CLRS sec 16.1 e 16.2.
Transparências.
[pdf] [ps.gz]
- 15 de maio
Matéria da prova: filas de prioridade,
heapsort, cota inferior para ordenação, ordenação em tempo
linear, programação dinâmica.
- 17 de maio (aula 18)
- Coloração de coleção de intervalos
- Um problema de escalonamento
Referências bibliográficas: KT secs 4.1 e 4.2.
Transparências.
[pdf] [ps.gz]
- 22 de maio (aula 19)
- Códigos de Huffman
- Lista 5 - a ser disponibilizada
Transparências.
[pdf] [ps.gz]
Referências bibliográficas: CLRS sec 16.3.
- 24 de maio (aula 20)
- Análise amortizada: contador binário e tabelas dinâmicas
- Análise agregada, por créditos e por potencial
Transparências.
[pdf] [ps.gz]
Referências bibliográficas: CLRS cap 17.
- 25 e 27 de maio: Terceira semana de break (Corpus Christi; não haverá aula)
Last modified: Thu May 23 18:34:28 BRT 2013