Programação das aulas de MAC5711

Primeiro semestre de 2004

Março

• 9 de março (aula 1):
  • Introdução.
  • Qual das duas funções você prefere? [f1][f2]
    Pense, decida e depois execute cada uma para algumas entradas. Escolha como entrada números entre 10 e 20. Aumente gradativamente se não der para sentir a diferença entre as duas e decida se a sua escolha foi boa.
• 11 de março (aula 2):
  • Por que desprezamos as constantes?
  • Ordenação - método de inserção.
  • Notação assintótica.
  • Chute a complexidade do algoritmo! [ps.gz][pdf]
  • Desafio 1.
  Leitura recomendada: CLR, sec 1.1 e 1.2, caps 2 e 3.
  Exercícios: 2-1 e 2-4 do CLR.
• 16 de março (aula 3)
  • Divisão e conquista
    
    
  • Mergesort
  • Resolução de recorrências.
  • Lista 1
  Leitura recomendada: CLR, sec 1.3, 1.4, 4.1 e 4.2.
  Exercícios: 1-2, 1-3, 4.2-2 e 4.2-3 do CLR.
• 18 de março (aula 4)
  • Um pouco mais sobre recorrências.
  • Quicksort - análise do pior caso.
  Leitura recomendada: CLR, cap 8.
  Exercícios: 8.3-2 e 8.4-1 e do CLR.
• 23 de março (aula 5)
  • Versões probabilísticas do quicksort.
  • Análise do caso médio de uma das versões probabilísticas do quicksort.
  • Discussão sobre análise de caso médio.
  • Lista 2
  Veja notas de aula. [ps] [pdf]
  Exercícios: 8.4-3 e 8.4-4 do CLR.
• 25 de março (aula 6)
  • Multiplicação de inteiros grandes.
  • Método de Strassen para multiplicação de matrizes.
  Leitura recomendada: Parte suplementar da aula 5 (pag 109-111) das notas de aula do David Mount e sec 31.2 do CLR (sec 28.2 do CLRS).
  Exercícios: 31.2-1, 31.2-3 e 31.2-6 do CLR.
• 30 de março (aula 7)
  • Seleção.
  • Limite inferior para o cálculo do máximo (ou mínimo).
  • Heaps.