Informacoes basicas

  • Aulas: Seg/Qua 9-11, L506/L150

  • 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

  • Data das provas
    • P1: 11-Abril
    • P2: 16-Maio
    • P3: 22-Junho
    • Prova final: 29-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


Topicos em ordem cronologica (sujeito a atualizacoes)


Topico Material Lista exercicios Livro texto
Introducao Intro, Stable Matching, demo Stable Matching
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 [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]
Aula de BST do Erik Demaine (MIT) [Dasgupta Cap 3 e 4]
Animacao Dijkstra
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 Lista de exercicios P2
Lista de exercicios P2 (2)
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)]
Maxflow Maxflow, Demo Ford-Fulkerson, Aplicacoes [KT Cap 7]
Min cost flow Min cost flow
Complexidade Reducoes e NP-completude [KT Cap 8]
Lista de exercicios P3
Lista de exercicios P3 (2)