Informacoes basicas

  • Aulas: Qua 13-16, sala RDC 511
  • Link zoom
  • 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)

  • Avaliaco
    • 2 provas (+ prova final)

  • Data das provas
    • P1: 24-Abril
    • P2: 26-Junho
    • Prova final: 3-Julho

  • Criterio de avaliacao:
    • Se (P1+P2)/2 >= 7, o(a) aluno(a) sera aprovado(a) com essa media sem direito a prova final
    • Se 6 <= (P1 + P2)/2 < 7, o aluno decide se quer fazer prova final; se sim, a prova final entra na nota final
    • Se (P1 + P2)/2 < 6, o aluno necessariamente faz prova final, e sua nota entra na nota final

    • Caso a nota da prova final entre na nota final, essa sera sera calculada NF = min {7.0, (PF+ max{P1,P2} ) /2 }
    • O aluno 'e aprovado caso a nota final NF seja pelo menos 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
Solucao alternativa problema 3 For's
[KT Cap 2]
Breve revisao de somatorios Somatorios [Cormen Cap A.2]
Algoritmos de ordenacao Algoritmos de ordenacao [Cormen Cap 2.3, 7.2, 8]
Animacao CountingSort
Heaps Heaps Exercicios dos slides
Lista exercicios P1 (parte 1)
[Cormen Cap 6]
Selecao em tempo linear Selecao em tempo linear
(Video do Tarjan sobre historia de selecao em tempo linear)
Algoritmos em grafos Algoritmos em grafos Lista exercicios P1 (parte 2) [KT Cap 3] [Cormen Cap 22.1, 22.2, 22.4]
Algoritmos gulosos Algoritmos gulosos [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 (anotacoes)
(execucao Interval Sched)
[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 P2