GBC052 - Análise de Algoritmos - 2º Sem. de 2017

Avisos

  • Notas do Trabalho 2
  • Ranking de kib*ms do Trabalho 2
  • Resolução da Prova 2: gabarito
  • Resolução da Prova 1: gabarito
    •

    Datas importantes

  • 29/09/2017 - Prova 1 - valendo 25 pontos
  • 01/11/2017 - Prova 2 - valendo 25 pontos
  • 20/12/2017 - Prova 3 - valendo 30 pontos
    •
  • 22/12/2017 - Prova Recuperação - valendo 30 pontos
    •

    Sobre a disciplina

  • Salas de aula: Quartas no 5R-A, sala 315, Quintas 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.

    • Trabalhos

  • Trabalho 2: hashing
  • Trabalho 1: Competition sort. Arquivos com exemplos de entradas possíveis. Apresentação em 03/11/2017
  • BASH script que será usado para medição dos tempos
  • Saída produzida na medição dos tempos
  • Outros exemplos de possíveis entradas
    •

    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 - Funções Geradoras Ordinárias
  • Lista 5 - Método simbólico e árvores
  • Lista 6 - Hashing
  • Lista 7 - Programação Dinâmica e exercícios do Livro do Cormen
  • Amortização: exercícios do Livro do Cormen
    •

    Aulas

  • 01 - Introdução
  • 02 - Análise Assintótica - caso médio
  • 02b - Caso médio Insertion Sort - códigos
  • 03 - Recorrências
  • 04 - Divisão e Conquista
  • 05 - Teorema Mestre
  • 06 - Funções Geradoras - Tabela de funções geradoras e operações
  • 07 - Árvores
    •

    Outras informações

  • Lib: General Purpose Hash Function Algorithms
  • Notas do Pagh sobre 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
  • Algoritmos dançados
  • 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
    •