MAC0338: 2010/1: Diario

MAC0338-2010: Diário

24/2 Q: Aula 1
- Exercícios preliminares
- Indução matemática
- Algoritmos recursivos
26/2 S: Aula 2
- Discussão da tarefa 1
- A função log
- Provas por indução matemática
- Algoritmos recursivos
- Introdução à notação O
- Busca em vetor ordenado
03/3 Q: Aula 3
- Discussão da tarefa 2 (busca binária)
- Invariantes e prova da correção de algoritmo iterativo
- Prova da correção de um algoritmo recursivo
- Consumo de tempo de algoritmo iterativo
- Piso e teto
05/3 S: Aula 4
- Consumo de tempo de algoritmo recursivo
- Recorrências
- Ordenação por inserção
- Algoritmo Mergesort
10/3 Q: Aula 5
- Discussão da tarefa 3
- Algoritmo Mergesort
- Solução de recorrências
- Notação assintótica
12/3 S: Aula 6
- Divisão e conquista
- Algoritmo Quicksort
17/3 Q: Aula 7
- Discussão da tarefa 4
- Solução de recorrências
- Algoritmo Quicksort: tempo médio e algoritmo aleatorizado
19/3 S: Aula 8
- Algoritmo rápida da mediana
- Algoritmo Heapsort
24/3 Q: Prova 1
26/3 S: Complemento da Prova 1
31/3 Q: Feriado (Semana Santa)
02/4 S: Feriado (Semana Santa)
07/4 Q: Aula 10
- Fila de prioridades
- O problema do segmento de soma máxima
- Tarefa 5, durante a aula.
09/4 S: Aula 11
- Subsequência crescente máxima
- Tarefa 6, durante a aula
- Tarefa 7, para 14/4
14/4 Q: Aula 12
- Multiplicação de inteiros e o algoritmo de Karatsuba e Ofman
- Tarefa 8, durante a aula
16/4 S: Aula 13
- Coleção disjunta máxima de intervalos
- Tarefa 9, para 23/4
21/4 Q: Feriado (Tiradentes)
23/4 S: Aula 14
- Coleção disjunta máxima de intervalos: algoritmo guloso
- O problema subset-sum
- Tarefa 10 (para 28/4)
28/4 Q: Aula 15
- O problema da mochila booleana
- Tarefa 11 (durante a aula)
30/4 S: Aula 16
- O problema da mochila booleana
- Um algoritmo de aproximação para o problema da mochila
05/5 Q: Não haverá aula (break)
07/5 S: Não haverá aula (break)
12/5 Q: Aula 17
- Códigos de Huffman
- Tarefa 12 (para 14/5)
14/5 S: Aula 18
- Códigos de Huffman
- Busca de uma palavra em um texto
19/5 Q: Prova 2
21/5 S: Aula 19
- Discussão da prova
26/5 Q: Aula 20
- Consumo amortizado de tempo
- Consumo amortizado de Constroi-Max-Heap
- Tabelas dinâmicas
28/5 S: Aula 21
- Tabelas dinâmicas
- Tarefa 15, para 9/6
02/6 Q: Break (por conta de Corpus Christi)
04/6 S: Break (por conta de Corpus Christi)
09/6 Q: Aula 22
- Discussão da Tarefa 14
- Discussão da Tarefa 15
- Intercalação de k arquivos
- Intercalação ótima de k arquivos
11/6 S: Aula 23
- Árborescência maximal de peso mínimo em digrafos simétricos e algoritmo de Prim
16/6 Q: Aula 24
- Árborescência maximal de peso mínimo em digrafos simétricos e algoritmo de Prim
18/6 S: Aula 25
- Algoritmo probabilístico para corte mínimo em um grafo
23/6 Q: Aula 26
- Algoritmo probabilístico para corte mínimo em um grafo
- Ο, Ω e Θ versus pior caso, melhor caso e todos os casos
- Exemplo de análise probabilística
25/6 S: Sem aula, por conta da Copa do Mundo
30/6 Q: Prova 3
02/7 S: Aula 27
- Sem aula, por conta da Copa do Mundo.
  Mas estarei a minha sala, caso você queira conversar.