Programação das aulas de MAC338

Primeiro semestre de 2013

CLRS refere-se ao livro de Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms, 3a edição
(cuidado que as seções mudam de uma edição para a outra),
SW refere-se ao livro de Sedgewick e Wayne, Algorithms, e
KT refere-se ao livro de Kleinberg e Tardos, Algorithm Design.

Fevereiro

27 de fevereiro (aula 1):
- Introdução [pdf] [ps.gz]
- Por que ignorar as constantes?
- Notação O (Oh grande)
Transparências: [pdf]
Leitura recomendada: CLRS, secs 1.1, 1.2, 2.1 e 2.2.

Março

1 de março (aula 2):
- Notação assintótica
- Crescimento de funções
- Análise de pior caso, melhor caso e caso médio do InsertionSort
Transparências: [pdf]
Leitura recomendada: CLRS, sec 3.1 e 3.2. Se tiver dificuldades com a parte matemática, revise o material coberto nos apêndices A e parte do C do CLRS.
6 de março (aula 3):
- Divisão e conquista
- Mergesort
- Recorrências
- Lista 1
Transparências: [pdf]
Leitura recomendada: CLRS, sec 2.3.
8 de março (aula 4):
- Mais sobre recorrências
- Cálculo do segmento de soma máxima
Transparências. [pdf]
Leitura recomendada: CLRS, sec 4.1 e 4.3.
13 de março (aula 5)
- Divisão e conquista
- Multiplicação de inteiros grandes: algoritmo de Karatsuba
- Multiplicação de matrizes: algoritmo de Strassen
Transparências. [pdf]
Leitura recomendada: sec 4.2 do CLRS e sec 5.5 do KT.
15 de março (aula 6)
- Quicksort
- Análises de pior e melhor caso
- Lista 2
Transparências. [pdf]
Leitura recomendada: parte do cap 7 do CLRS.
20 de março (aula 7)
- Análise probabilística
- Cálculo do máximo
- Análise do caso médio do Quicksort
Transparências. [pdf]
Leitura recomendada: CLRS cap 7 e CLRS secs 5.1 e 5.2, apêndices C.1 a C.3, secs 7.1 e 7.2.
22 de março (aula 8)
- Quicksort probabilístico
- Consumo de tempo esperado
- Select probabilístico
- Consumo de tempo esperado
Transparências. [pdf]
Leitura recomendada: CLRS sec 7.3, 7.4, 9.1 e 9.2.
27 e 29 de março: Semana Santa (não haverá aula)

Abril

Maio

Last modified: Fri Apr 26 10:24:03 BRT 2013