Programação das aulas de MAC5711

Segundo semestre de 2002

Agosto e setembro

• 12 de agosto (aula 1):
  • Introdução [ps.gz][pdf].
  • Qual das duas funções você prefere? [f1][f2]
  • Ordenação - método de inserção.
  Leitura recomendada: CLR, sec 1.1 e 1.2.
• 15 de agosto (aula 2):
  • Complexidade de tempo e notação assintótica.
  • Lista 1: 2-1 e 2-4 do CLR (para dia 22/8).
  Leitura recomendada: CLR, cap 2 e 3.
• 19 de agosto (aula 3)
  • Divisão e conquista - mergesort.
  Exercícios: 4.2-2 e 4.2-3 do CLR.
  Leitura recomendada: CLR, sec 1.3, 1.4, 4.1 e 4.2.
• 22 de agosto (aula 4)
  • Quicksort - análise do pior caso.
  Leitura recomendada: CLR, cap 8.
• 26 de agosto (aula 5)
  • Quicksort - análise e discussão do caso médio.
  • Listas 2 e 3.
• 29 de agosto (aula 6)
  • Seleção.
  • Limite inferior para o cálculo do máximo (ou mínimo).
  • Heapsort.
  Leitura recomendada: CLR, sec 7.1, 7.2 e 7.4.
• 9 de setembro (aula 7)
  • Construção de um heap (CLR, sec 7.3).
  • Filas de prioridade (CLR, sec 7.5).
  • Limite inferior para ordenação (CLR, sec 9.1) [ps.gz][pdf].
  • Lista 4.
• 12 de setembro (aula 8)
  • Algoritmos lineares de ordenação.
  Leitura recomendada: CLR, sec 9.2 e 9.3.
• 16 de setembro
  • Prova 1
  Matéria provável da prova: notação assintótica, recorrências, ordenação (capítulos 1, 2.1, 4.1, 4.2, 7, 8, 9.1, 9.2 e 9.3 do CLR).
• 19 de setembro (aula 9)
  • Resolução de exercícios dos exames preliminares.
• 23 de setembro (aula 10)
  • Algoritmos para o problema do k-ésimo mínimo.
  Leitura recomendada: CLR, cap. 10 e notas de aula.
• 26 de setembro (aula 11)
  • Método de Strassen, para multiplicação de matrizes.
  • Lista 5.
  Leitura recomendada: CLR, sec 31.2.
• 30 de setembro (aula 12)
  • Programação dinâmica
  • Multiplicação de seqüências de matrizes.
  • Árvore de busca ótima.
  Leitura recomendada: CLR, sec 16.1 e 16.2 e cópia de dois livros que coloquei no xerox sobre árvores de busca ótima.