Somebody once asked John Hopcroft about the problem of P and NP. He answered: “On Tuesdays, I try to prove that they are equal, on the rest of the week - that they are different.” I believe that he has reduced the time to try to show that they are equal to Sunday afternoons.

Professor: Marcus Ritt
Total hours: 30 h (in 15 lectures of 2h)
Credits: 2
Summary: Algorithms: Analysis of algorithms. Main techniques for designing algorithms.
Time and room: Tue/Thu 8.30, 113/43425.
Consultation hours: By appointment.
Details: On the homepage of the course at PPGC.

• First lecture: Tue, Oct 10.

• Homepage of CMP155 (Análise e Desenvolvimento de Algoritmos) in 2011/1, 2010/1, 2008/1 and 2007/1.
• Homepage of CMP601 in 2022/1, 2020/2, 2020/1, 2019/2, 2018/1, 2016/2, and 2015/1.
• Lecture notes (in Portuguese, updated Junho 2022).

See the homepage of the course at PPGC. Specifically in this source we have

• An exam (see the agenda above), which contributes 80% of the final grade
• Five exercise lists, which contribute 20% of the final grade
• A retake exam, for those who participated in all activities, whose final grade is below 6. To pass, you need a grade of 6 in this exam.

• Template (LaTeX,PDF) for exercise lists.

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
• Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Freeman, 1979.
• E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1984.
• Laira Vieira Toscani and Paula A. S. Veloso. Complexidade de Algoritmos. Editora Sagra Luzzatto, 2a edition, 2005.
• 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.
• Bernhard H. Korte and Jens Vygen. Combinatorial optimization theory and algorithms. Springer, 4th edition, 2008. INF 65.012.122 K85c.
• Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
• Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
• S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algoritmos. McGraw-Hill, 2009.