Analise de Algoritmos

Informacoes basicas

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

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)