Programação das aulas de MAC5711

Segundo semestre de 2002

Outubro

• 3 de outubro (aula 13)
  • Programação dinâmica.
  • Subseqüência comum de comprimento máximo.
  • Algoritmo de Floyd para caminhos mínimos.
  Leitura recomendada: CLR, sec 16.3 e sec 26.2.
• 10 de outubro (das 8:30 às 10 horas)
  • Resolução de exercícios.
• 14 de outubro (aula 14)
  • Análise amortizada.
  • Exemplo 1: contador binário
  • Exemplo 2: pilha com operações POP, PUSH e MULTIPOP.
  Leitura recomendada: CLR, cap 18.
• 17 de outubro (aula 15)
  • Análise amortizada.
  • Estrutura de dados para conjuntos disjuntos (union-find).
  Leitura recomendada: CLR, cap 22.
• 21 de outubro
  • Prova 2.
  Matéria da prova: k-ésimo mínimo, medianas, Strassen, programação dinâmica e análise amortizada.
• 24 de outubro (aula 16)
  • Union-find.
  • Grafos.
  Leitura recomendada: CLR, início da sec 22.4 e sec 23.1.
• 28 de outubro (aula 17)
  • Algoritmos de busca em grafos.
  Leitura recomendada: CLR, cap 23.
• 31 de outubro (aula 18)
  • Algoritmos gulosos.
  • Árvore geradora de custo mínimo.
  Leitura recomendada: CLR, cap 24.

• 4 de novembro (aula 19)
  • Busca de padrão: algoritmo ingênuo e KMP.
  Leitura recomendada: CLR, sec 34.1 e 34.4.
• 7 de novembro (aula 20)
  • Busca de padrão: algoritmo KMP
  Leitura recomendada: CLR, sec 34.4
• 18 e 21 de novembro (aulas 21 e 22)
  • Complexidade computacional.
  Leitura recomendada: CLR, sec 36.1 e 36.2.
  Uma introdução sucinta a algoritmos de aproximação [ps.gz]
  Demonstrações Transparentes e a Inaproximabilidade de Aproximações (livro do Prof. Yoshi e do Prof. José Augusto) [ps.gz]
  
• 25 de novembro
  • Prova 3
  Matéria provável da prova: union-find, grafos, busca de padrão e complexidade computacional.
• 28 de novembro (aula 23)
  • Mais sobre complexidade computacional.