Algoritmos avançados (INF 5016/CMP 588) (2013/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-15.10, ANFA, prédio 43425.
Consultas: Seg/Qua, 15.10-16.00.
Detalhes: Vê o programa e página da PPGC.

Resultados

Notícias

Primeiro dia de aula: 5 de agosto.
Todos os laboratórios: sala 101, prédio 67.

Materias

Página da disciplina em 2012/2, 2011/2, 2010/2 e 2009/1.
Notas de aula (atualizado 16/10/2013).
Algumas demonstrações de algoritmos.
Dicas para os trabalhos experimentais.

Aulas

No.	Data	Tópicos	Notas pág.	Leitura
1	05/08	Introdução. Heaps binários.	3-9	KT2.5,C6
2	07/08	Laboratório 1
3	12/08	Heaps binomiais.	9-13	K8,C19
4	14/08	Laboratório 2
5	19/08	Fluxo em redes 1.	29-34	KT7.{1,2}
6	21/08	Laboratório 3.
7	26/08	Fluxo em redes 2.	34-40	KT7.{2,3}
8	28/08	Laboratório 4.
	02/09
9	04/09	Laboratório 5 (aula a distância).
10	09/09	Laboratório 6 (aula a distância).
11	11/09	Laboratório 7 (aula a distância).
12	16/09	Fluxo em redes 3 .	40-43	KT7.4
13	18/09	Emparelhamentos 1.	44-46	KT7.5,K19
14	23/09	Emparelhamentos 2.	47-54	K20
15	25/09	Laboratório 8.
16	30/09	Emparelhamentos 3.	47-54	K20
17	02/10	Laboratório 9.
18	07/10	Hashing 1.	59-62
19	09/10	Laboratório 10.
20	14/10	Hashing 2.	62-67
21	16/10	Laboratório 11.	55-58	KT13.6,C11
	21/10	Semana acadêmica
	23/10	Semana acadêmica
	28/10	Dia do servidor público
	30/10	Sem aula
22	04/11	Aproximação 1.		V4
23	06/11	Laboratório 12.
24	11/11	Aproximação 2.
25	13/11	Randomização 1.		MU1,KT13.2
26	18/11	Randomização 2.		C31.8
27	20/11	Laboratório 13 (103).
	25/11	Sem aula		KT10.1
28	27/11	Laboratório 14.
29	02/12	Prova
30	04/12	Parametrização.		KT10.1
	09/12	Prova de recuperação.

	20/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.