Projeto e Analise de Algoritmos
2023.1
Informacoes basicas
Aulas:
Seg 9-12
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: 19-Junho
Prova final: 26-Junho
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]
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