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

Bem-vindo.

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, 109/43413.
Consultas: a combinar.
Detalhes: Vê o programa e página da PPGC.

• Trabalhos
• Notas
• Frequência

• As aulas recomeçam no dia 1 de julho.
• 18 de março: 1o dia de aula.

• Página da disciplina em 2022/2, 2021/1, 2017/1, 2015/2, 2014/2, 2013/2, 2012/2, 2011/2, 2010/2 e 2009/1.
• Notas de aula (atualizado 8/4/2024).
• Algumas demonstrações de algoritmos.
• Dicas para os trabalhos experimentais.

No.	Data	Tópicos	Notas cap.	Exercícios	Soluções	Leitura
1	18/03	Algoritmo de Dijkstra e Heaps binários.	1.1-1.4			KT2.5,C6
2	20/03	Laboratório 1 (101, Dijkstra).				JEA, AM
3	25/03	Árvores geradoras, Fast marching method e A*.	1.1-1.4
4	27/03	Laboratório 2 (101, Dijkstra).
5	01/04	Tópicos em caminhos mais curtos.	1.5			KT4
6	03/04	Laboratório 3 (101).
7	08/04	Fluxos em redes 1.	1.6			KT7.{1,2}
8	10/04	Laboratório 4 (101).
9	15/04	Fluxo em redes 2 (113/43425).	1.6			KT7.{2,3}
10	17/04	Laboratório 5 (102).
11	22/04	Fluxo em redes 3.	1.6			KT7.4
12	24/04	Laboratório 6 (101).
13	29/04	Emparelhamentos 1.	1.7			KT7.5,K19
	01/05	Dia do Trabalho
		06/05-30/06: Suspensão
14	01/07	Emparelhamentos 2.	1.7			K20
15	03/07	Laboratório 7 (101).
16	08/07	Emparelhamentos 3.	1.7			K20
17	10/07	Laboratório 8 (101).
18	15/07	Emparelhamentos 4.	1.7			K20
19	17/07	Laboratório 9 (102).
20	22/07	Randomização 1.	4.1			MU1,KT13.2
21	24/07	Laboratório 10 (102).
22	29/07	Randomização 2.	4.2			C31.8
23	31/07	Laboratório 11 (102).
24	05/08	Randomização 3.	4.3-4.4			C31.8
25	07/08	Laboratório 12 (101).
26	12/08	Randomização 4..
27	14/08	Laboratório 13 (101).
28	19/08	Cobertura por conjuntos.
29	21/08	Laboratório 14 (105).
30	26/08	Prova
		Provas de recuperação (a serem combinadas).
	31/08	Término oficial das aulas.

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

• 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.