PGC101 - Análise de Algoritmos - 2º Sem. de 2019
Notas
Notas - Prova 2
Datas importantes
18/09/2019 - Prova 1 - 25 pontos
09/10/2019 - Apresentação do trabalho 1 - valendo 10 pontos
16/10/2019 - Prova 2 - valendo 25 pontos
11/12/2019 - Prova 3 - valendo 30 pontos
18/12/2019 - Apresentação de trabalho 2 - 10 pontos
Sobre a disciplina
Salas de aula: Quartas-feiras, sala de seminários da pós-graduação bloco 1B, 19h às 22h30
Ementa
Livro sobre Análise de Algoritmos: AdA An Introduction to the Analysis of Algorithms (2nd edition) by Robert Sedgewick and Philippe Flajolet
Livro sobre implementação de Algoritmos: Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
Livro sobre Algoritmos e Teoria de Complexidade: CLRS - Cormen, Thomas H. et. al. Algoritmos: Teoria e Prática.
Exercícios
Lista 0 - Introdução
Lista 1 - Recorrências
Lista 2 - Escrita e análise de Recorrências
Lista 3 - Divisão e conquista
Lista 4 - Teoremas Mestres para Divisão e conquista
Lista 5 - Funções Geradoras Ordinárias
Lista 6 - Método simbólico e árvores
Lista 7 - Hashing
Lista 7 - Programação Dinâmica e exercícios do Livro do Cormen
Lista 8 - Análise amortizada
Aulas
01 - Introdução
02 - Análise Assintótica - caso médio
03 - Recorrências - Tabela de somas elementares
04 - Divisão e Conquista
05 - Teorema Mestre
06 - Funções Geradoras - Tabela de funções geradoras e operações
07 - Árvores
08 - Hashing
09 - Programação dinâmica
11 - Análise amortizada (custo médio de operações)
Outras informações
Lib: General Purpose Hash Function Algorithms
Notas do Pagh sobre Cuckoo Hashing
Análise de Cuckoo Hashing
Aula sobre introdução a Hashing por E. Demaine (MIT)
Análise de Algoritmos por Don Knuth, Stanford
Quicksort em três partes é ótimo! por R. Sedgewick
Comparação animada de algoritmos
Problemas de divisão e conquista
Nível 2 - Skyline Problem
Nível 3 - INVCNT
Nível 3 - BALDES
Problemas de ordenação
Nível 1 - IMPEDIDO
Nível 1 - WCW
Nível 2 - LSALAO
Problemas de recursão, programação dinâmica e relacionados
Nível 1 -F91
Nível 1 -CAIXAS
Nível 2 -MOEDAS
Nível 2 -PARQUE
Nível 2 -ROBUSMG
Nível 2 -TESOURO
Nível 2 -BAPOSTAS
Nível 2 -COMCAMEL
Nível 2 -DESCULPA
Nível 3 -GENEAL
Nível 3 -MINIMO
Nível 3 -NUVEMMG
Nível 4 -LCAIXA
Nível 4 -ZAK