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.

Professors: Álvaro Freitas Moreira, Marcus Ritt
Total hours: 60 h (in 30 lectures of 2h)
Credits: 4
Summary: Theory of Computation: Models of computation. Limitation of formal systems. Complexity theory. Algorithms: Analysis of algorithms. Main techniques for designing algorithms.
Time and room: Tue/Thu 10.30, upper lecture hall, building 43413 (67).
Consultation hours: Thu 14.30, room 216.
Details: On the homepage of the course at PPGC.

• Second exam: Jun 28, 2018. The exam will take 2.5 hours.
• Lecture notes updated.

• Results of the first qualification exam.
• Results of the second qualification exam.
• Results of the course.

• Homepage of CMP155 (Análise e Desenvolvimento de Algoritmos) in 2011/1, 2010/1, 2008/1 and 2007/1.
• Homepage of CMP601 in 2015/1, and 2016/2.
• Lecture notes (in Portuguese, updated 19/5/2018).
• Some comments on the qualification exam.

See the homepage of the course at PPGC.

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