Programação das aulas de MAC338

Primeiro semestre de 2011

Fevereiro

• 23 de fevereiro (aula 1):
  • Introdução [pdf] [ps.gz]
  • Por que ignorar as constantes?
  • Notação O (Oh grande)
  • Um primeiro exercício [pdf] [ps.gz]
  • Os fontes das duas funções. A partir de que valores você sente a diferença? [f1] [f2]
  Transparências: [pdf]
  Leitura recomendada: CLRS, secs 1.1, 1.2, 2.1 e 2.2.

• 25 de fevereiro (aula 2):
  • Notação assintótica
  • Comentários sobre o exercício da aula passada [f3] [f4]
  • Crescimento de funções
  • Contar inversões
  Transparências: [pdf]
  Leitura recomendada: CLRS, sec 3.1.

• 2 de março (aula 3):
  • Divisão e conquista
    
    
  • Mergesort
  • Conta inversões
  • Recorrências
  Transparências: [pdf]
  Leitura recomendada: CLRS, sec 2.3, 3.2, 4.1 e 4.2.

• 4 de março (aula 4):
  • Recorrências
  • Cálculo do segmento de soma máxima
  • Lista 1
  Transparências. [pdf]
  Leitura recomendada: CLRS, sec 4.1 e 4.2.

• 9 e 11 de março: carnaval; não haverá aula.

• 16 de março (aula 5)
  • Cálculo do segmento de soma máxima (cont.)
  • Divisão e conquista
  • Multiplicação de inteiros grandes: algoritmo de Karatsuba
  • Multiplicação de matrizes: algoritmos de Strassen
  Transparências. [pdf]
  Leitura recomendada: KT sec 5.5 e CLRS sec 28.2.

• 18 de março (aula 6)
  • Análise probabilística
  • Cálculo do máximo
  • Lista 2
  Transparências. [pdf]
  Leitura recomendada: CLRS 5.1, C.2 e C.3.

• 23 de março (aula 7)
  • Quicksort
  • Análises de pior e melhor caso
  • Análise do caso médio
  Transparências. [pdf]
  Leitura recomendada: CLRS cap 7.

• 25 de março (aula 8)
  • Quicksort probabilístico
  • Análise do caso médio
  • Filas de prioridade (heaps)
  • Heapsort
  • Lista 3
  Transparências. [pdf]
  Leitura recomendada: CLRS sec 7.4 e cap 6.

• 30 de março (aula 9)
  • Aula de exercícios

Abril

Maio