CMP 601: Algorithms and Theory of Computation (2022/1)

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.

General information

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, 108/43413.
Consultation hours: By appointment.
Details: On the homepage of the course at PPGC.
Note: The course will be split during the semester into two courses.

News

First lecture: Tue, Jun 14.

Results

Additional material

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

Lectures

No.	Date	Topics	Chap. in notes	Exercises	Solutions	Reading
		Algorithms
1	14/06	Administrativa. Introduction.	1			1.1
	16/06	Corpus Cristi
2	21/06	Basics of analysis and representative problems.				1.2
3	23/06	Basics of analysis and representative problems.	2			2
	24/06	Qualification exam algorithms (8.30, AUD-0)		E	S
	24/06	Qualification exam theory (13.30, 109, 43413)
4	28/06	Graph algorithms 1.				3.[123],4.4
5	30/06	Graph algorithms 2.				3.[46]
6	05/07	Graph algorithms 3.		E1	S1	3.5
7	07/07	Greedy algorithms 1.	4			4.[12]
8	12/07	Greedy algorithms 2.	4			4.5
9	14/07	Greedy algorithms 3.	4			4.9
10	19/07	Divide-and-conquer algorithms 1.	5	E2	S2	5.[123]
11	21/07	Divide-and-conquer algorithms 2.	5			5.[45]
12	26/07	Divide-and-conquer algorithms 3.	5			5.6
13	28/07	Dynamic programming 1.	6	E3	S3	6.[12]
14	02/08	Dynamic programming 2.	6			6.[45]
15	04/08	Dynamic programming 3.	6	E4	S4	6.[67]
		Theory of computation
16	09/08	Theory 1: Introduction – Noncomputability
17	11/08	Theory 2: Introduction – Intractability
18	16/08	Theory 3: Introduction – NP-complete problems
19	18/08	Theory 4: Turing Machines
20	23/08	Theory 5: Undecidability
21	25/08	Theory 6: Reducibility
22	30/08	Theory 7: Time Complexity I
23	01/09	Theory 8: Time Complexity II
24	06/09	Theory 9: Time Complexity III
25	08/09	Theory 10: Time Complexity IV
26	13/09	Theory 11: Exercises
27	15/09	Theory 12: Space Complexity I
	20/09	Revolução Farroupilha
28	22/09	Theory 13: Intractability
	27/09	Semana Acadêmica
	29/09	Semana Acadêmica
29	04/10	Theory 14: Exercises
30	06/10	Theory 15: Exercises
	20/10	Official end of lecture period 2022/2.

Evaluation

See the homepage of the course at PPGC.

Material

Template (LaTeX,PDF) for exercise lists.

Bibliography

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.