GBC052 - Análise de Algoritmos - 1º Sem. de 2019
Avisos
Notas da Prova 3
Gráficos de tempos: modelo 0, modelo 1, modelo 13
Descrição do trabalho 1 - entrega e apresentação 10/05
Gerador de dados aleatórios - A corretude da ordenação pode ser verificada usando como referência a saída do comando "java Generator 12 10 | sort -g" - ATENÇÃO: para facilitar, serão usados apenas os casos: inteiros desordenados (opção 0), inteiros ordenados (opção 1) e ACTG (opção 13)
Datas importantes
17/04/2019 - Prova 1 - valendo 25 pontos
17/05/2019 adiada para 22/05/2019 - Prova 2 - valendo 25 pontos
05/07/2019 - Prova 3 - valendo 30 pontos
10/07/2019 - Apresentações Trabalho 2
12/07/2019 -Prova de recuperação
Sobre a disciplina
Salas de aula: Quartas no 5R-A, sala 200, Sextas no 5R-A, sala 200
Plano da disciplina
Ficha da disciplina (Curso: Ciência da Computação)
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