Algoritmos avançados (2010/2)

Beware of bugs in the above code; I have only proved it correct, not tried it. (Donald Knuth)

Bem-vindo.

Informações gerais

Carga horária: 60 h (em 30 aulas de 2h)
Créditos: 2+2
Súmula: Algoritmos, estruturas de dados e técnicas algoritmicas avançadas: algoritmos randomizados, algoritmos de aproximação, algoritmos parametrizados.
Turma: U.
Horário/Sala: Seg/Qua 13.30, ANFA (Seg), Lab. 101 (Qua).
Consultas: Qua 15.30.
Detalhes: Vê o programa.

Resultados

Notícias

Prazo final para trabalhos 1-4: 15/11/2010.

Materias

Página da disciplina em 2009/1
Notas de aula (atualizado 18/11/2010)
Algumas demonstrações de algoritmos.
Dicas para os trabalhos experimentais

Aulas

No.	Data	Tópicos	Notas pág.	Exercícios	Soluções	Leitura
1	09/08	Introdução. Heaps binários.	3-9			KT2.5,C6
2	11/08	Laboratório 1.
3	16/08	Heaps binomiais.	9-13			K8,C19
4	18/08	Laboratório 2.
5	23/08	rp-heaps.	18-27			Haeupler et al. 2009
6	25/08	Laboratório 3.
7	30/08	Fluxo em redes 1.	29-34			KT7.{1,2}
8	01/09	Laboratório 4.
	06/09	Sem aula.
9	08/09	Fluxo em redes 2.	34-40			KT7.{2,3}
10	13/09	Fluxo em redes 3.	40-43			KT7.4
11	15/09	Laboratório 5.
	20/09	Revolução Farroupilha
12	22/09	Laboratório 6.
13	27/09	Emparelhamentos 1.	44-46			KT7.5,K19
14	29/09	Laboratório 7.
15	04/10	Emparelhamentos 2.	47-54			K20
16	06/10	Laboratório 8.
17	11/10	Emparelhamentos 3.	55-58			KT13.6,C11
18	13/10	Laboratório 9.
	18/10	Semana acadêmica
	20/10	Semana acadêmica
19	25/10	Hashing 1.	59-62
20	27/10	Hashing 2.	62-67
21	01/11	Dia do funcionário público.
22	03/11	Laboratório 10.
23	08/11	Aproximação.				V4
24	10/11	Laboratório 12.
	15/11	Proclamação da república do Brasil
	17/11	Laboratório 11.
25	22/11	Randomização 1.				MU1,KT13.2
26	24/11	Laboratório 13.
27	29/11	Randomização 2.				C31.8
28	01/12	Laboratório 14.
29	06/12	Parametrização.				KT10.1
30	15/12	Prova		P1	S1
	20/12	Prova de recuperação.

	23/12	Término oficial das aulas.

Livros: KT=Kleinberg/Tardos. K=Kozen, C=Cormen, et al.,V=Vazirani, MU=Mitzenmacher/Upfal

Bibliografia

Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
Jon Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley, 2005.
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
Rolf Niedermeier. Invitation to fixed-parameter algorithms. Habilitationsschrift, Universität Tübingen, WSI für Informatik, Germany, September 2002.
Dexter Kozen. The design and analysis of algorithms. Springer, 1991.
Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Dover edition, 1982.