Informacoes basicas

  • Aulas: Seg/Qua 9-11, L304

  • Material principal: Slides das aulas, listas de exercicios, exercicios dos livros-texto

  • Livros-texto
    • Algorithm Design. Kleinberg e Tardos
    • Introduction to Algorithms. Cormen, Leiserson, Rivest, e Stein
    • Algorithms. Dasgupta, Papadimitriou, e Vazirani
    • Estrutura de Dados e Seus Algoritmos. Markezon e Szwarcfyter
    • Cracking the Coding Interview. McDowell (exercicios)

  • Data das provas
    • P1: 2-Abril
    • P2: 14-Maio
    • P3: 18-Junho
    • Prova final: 27-Junho

  • Criterio de avaliacao: Categoria 4
    • G1,G2 e G3 com mesmo peso, com prova final (G4)
    • Se G1,G2 e G3 forem maior ou igual a 3,0 e a media maior ou igual a 5,0, entao: NF = G1 + G2 + G3/3
    • Caso contrario, o aluno faz a G4
      • se G4 maior ou igual a 3,0, entao: NF = (Gm + Gn + G4)/3, aonde Gm e Gn sao as maiores notas de G1, G2 e G3
      • se G4 menor que 3, entao: NF = (G1 + G2 + G3 + G4 * 3)/6


Provas anteriores

Provas anteriores (AA e PAA)


Topicos em ordem cronologica (sujeito a atualizacoes)


Topico Material Lista exercicios Livro texto
Introducao Intro
Basico de analise de algoritmos Basico analise algoritmos Lista analise algoritmos, solucoes parciais [KT Cap 2]
Algoritmos de ordenacao Algoritmos de ordenacao [Cormen Cap 2.3, 7.2, 8]
Animacao CountingSort
Breve revisao de somatorios Somatorios [Cormen Cap A.2]
Heaps Heaps Lista exercicios P1 [Cormen Cap 6]
Selecao em tempo linear Selecao em tempo linear
Algoritmos em grafos Algoritmos em grafos [KT Cap 3] [Cormen Cap 22.1, 22.2, 22.4]
Animacao Dijkstra Lista de exercicios P2 [Dasgupta Cap 3 e 4]
Lista de exercicios P2 (2) [Dasgupta Cap 3 e 4]
Metodo guloso Slides [KT Cap 4] [Cormen Cap 23, 24.3]
Animacao interval scheduling
Animacao interval partitioning
Divisao e conquista Divisao e conquista [KT Cap 5]
Animacao Count Inversion
Programacao dinamica Programacao dinamica [KT Cap 6]
Subestruturas otimas comuns (Dasgupta at al.) [Nota: existem tambem variacoes onde item xi forcado estar em OPT(i)]
Outra perspectiva de programacao dinamica
Lista de exercicios P3
Lista de exercicios P3 (1)
Lista de exercicios P3 (2)