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 (Seg), Lab. 104 (Qua), prédio 43425.
Consultas: TBD.
Detalhes: Vê o programa.

Por razões técnicas, a disciplina foi dividida em duas disciplinas de dois créditos. Eles devem ser selecionados em conjunto:

• INF05504: TÓPICOS ESPECIAIS EM COMPUTAÇÃO V
• INF05505: TÓPICOS ESPECIAIS EM COMPUTAÇÃO VI

• Trabalhos
• Notas

• Aula de laboratório no dia 03/06 na sala 103!

• Notas de aula (atualizado 13/6/2009)
• Algumas demonstrações de algoritmos.
• Dicas para os trabalhos experimentais

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.
• Vijay V. Vazirani. Approximation algorithms. Springer, 2001.
• 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.