Programação das aulas de MAC338

Primeiro semestre de 2005

Março

• 2 de março (aula 1):
  • Introdução. [ps.gz][pdf]
  • Exercício 1 [ps.gz][pdf]. Qual das duas funções você achou que era mais rápida? [f1][f2]
    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.
  • Ordenação - método de inserção.
  Transparências [pdf] [ps.gz] (Essas excelentes transparências foram feitas pelos Professores Paulo Feofiloff e Coelho.)
  Leitura recomendada: CLR, sec 1.1 e 1.2.
• 4 de março (aula 2):
  • Exercício 1 - Discussão.
    Olhe as 4 funções e execute cada um dos programas para alguns valores de x e y.
    Sinta a diferença de comportamento entre eles. [f1][f2] [f3][f4]
    
  • Notação assintótica.
• 9 de março (aula 3)
  • Exemplos de uso de notação assintótica.
  • Notação assintótica em equações.
  • Intercalação.
  • Lista 1 [pdf] [ps.gz]
  Transparências. [pdf] [ps.gz]
• 11 de março (aula 4)
  • Divisão e conquista
    
    
  • Mergesort
  • Resolução de recorrências.
  Transparências. [pdf] [ps.gz]
• 16 de março (aula 5)
  • Mais sobre recorrências...
  • Mais um exemplo de uso de divisão e conquista: segmento de soma máxima.
  Transparências. [pdf] [ps.gz]
  Referência bibliográfica: capítulo 8 do livro do Bentley, Programming Pearls: Algorithm Design Techniques, Addison-Wesley, 1986.
• 18 de março (aula 6)
  • Multiplicação de inteiros grandes
  • Algoritmos de Strassen
  • Lista 2 [pdf] [ps.gz]
  Transparências. [pdf] [ps.gz]
  Referências bibliográficas: CLRS 2.1-2.2, 28.2, Aho & Ulmann 3.3 e 3.6.
  Para mais sobre algoritmos recursivos, veja as notas de aula de AA do Jeff Edmonds.
• 30 de março (aula 7)
  • Análise de caso médio - cálculo do máximo.
  • Um pouco mais sobre recorrências.
  • Quicksort - análise do pior caso.
  • Lista 3 [pdf] [ps.gz]
  Transparências. [pdf] [ps.gz]
  Referências bibliográficas: CLRS sec 5.1, C.2, C.3, cap 7.

Abril