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