Informacoes basicas

  • Comunicado: Nao teremos a aula do dia 26/Ago

  • Aulas: Segundas 1-4pm

  • 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: 7-Outubro
    • P2: 2-Dezembro
    • PF: 9-Dezembro

  • 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 [KT Cap 2]
Somatorios Somatorios
Algoritmos de ordenacao Algoritmos de ordenacao
Heaps Heaps [Cormen Cap 6]
Selecao em tempo linear Selecao em tempo linear
Algoritmos em grafos Algoritmos basicos Lista de exercicios P1 [KT Cap 3] [Cormen Cap 22.1, 22.2, 22.4]
Animacao Dijkstra Lista de exercicios P1 (2) [Dasgupta Cap 3 e 4]
Metodo guloso Metodo guloso [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 Inversions
Programacao dinamica Programacao dinamica
Obtendo solucao
Bellman-Ford
[KT Cap 6]
Exercicios P2 (0), Exercicios P2,
Exercicios P2 (2),
Exercicios P2 (3)
Outra perspectiva de programacao dinamica
Complexidade Reducoes e NP-completude [KT Cap 8]