CMP 625: Algorithms (2024/2)

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

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

News

Oct 4, 2024: second list of exercises and solution to the first list available
First lecture: Sep 24, 2024.

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 2022/1, 2020/2, 2020/1, 2019/2, 2018/1, 2016/2, and 2015/1.
Homepage of CMP612 in 2023/2.
Lecture notes (in Portuguese, updated June 2022).

Lectures

No.	Date	Topics	Chap. in notes	Exercises	Solutions	Reading
1	24/09	Administrativa. Introduction.	1	E1	S1	1
2	26/09	Introduction and representative problems.	2			1
3	01/10	Introduction and representative problems.	2			1
4	03/10	Exercises: Introduction.
5	08/10	Basics of analysis 1.	2	E2	S2	2
6	10/10	Basics of analysis 2.	2			2
7	15/10	Basics of analysis 3.	2			2
8	17/10	Exercises: Basics.
9	22/10	Graph algorithms 1.	4.2	E3	S3	3
10	24/10	Graph algorithms 2.	4.2			3
11	29/10	Graph algorithms 3.	4.2			3
12	31/10	Exercises: Graphs.
13	05/11	Greedy algorithms 1.	4	E4	S4	4
14	07/11	Greedy algorithms 2.	4			4
15	12/11	Greedy algorithms 3.	4			4
16	14/11	Exercises: Greedy algorithms.
17	19/11	Divide-and-conquer algorithms 1.	5	E5	S5	5
18	21/11	Divide-and-conquer algorithms 2.	5			5
19	26/11	Divide-and-conquer algorithms 3.	5			5
20	28/11	Exercises: Divide-and-conquer algorithms.
21	03/12	Dynamic programming 1.	6	E6	S6	6
22	05/12	Dynamic programming 2.	6			6
23	10/12	Dynamic programming 3.	6			6
24	12/12	Dynamic programming 4.	6			6
25	17/12	Exercises: Dynamic programming.
26	19/12	Exam.
23/12-04/01		Summer break
27	07/01	Review of the exam and exercises.
28	09-13/01	Retake Exams.
29	14/01	Additional topics and exercises in design techniques	4,5,6
30	16/01	Additional topics and exercises in design techniques	4,5,6
	18/01	Official end of the lecture period.	4,5,6
	20/01	Qualification exam.

Evaluation

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

An exam (see the agenda above), which contributes 60% to the final grade
Six exercise lists, which contribute 30% to the final grade
The presentation of two solved exercises in class, which contributes 10% to the final grade

Material

Template (LaTeX,PDF) for exercise lists.

Bibliography

Jon Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley, 2005.
Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
Jeff Erickson. Algorithms. 2019.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 4th edition, 2022.
Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algoritmos. McGraw-Hill, 2009.
Juraj Hromkovič. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
Bernhard H. Korte and Jens Vygen. Combinatorial Optimization – Theory and Algorithms. Springer, 6th edition, 2018. INF 65.012.122 K85c.