Algorithm Design 2024/2025

Algorithm Design 2024/2025

Master's degree in Engineering of Computer Science

Lectures will start on September 25th

Schedule of lessons: 

Tuesday, 12:00 - 14:00, Online  Zoom Link: https://uniroma1.zoom.us/j/81287647194?pwd=r3NKScpfZXZ1AfL3SMQ8aYyKSwyyag.1

Friday, 12:00 - 16:00, Room 29,  San Pietro in Vincoli 

Instructors: 

Prof. Stefano Leonardi          leonardi -- at -- diag.uniroma1.it

Prof. Aris Anagnostopoulos   aris--at--diag.uniroma1.it 

Office Hour: after the lecture of Friday or upon appointment at leonardi -- at -- diag.uniroma1.it

For the Algorithm Design Google Classroom site, enroll   https://classroom.google.com/c/NjI0NjE5ODQ3Njc3?cjc=pxamzsy

There are two possibilities for passing the exam: 

1) The first and most advised one is to submit the two partial exams that will be held in November and December  

2) The second is to attend the traditional written exam with oral discussion. 

The student who fails or does not submit the first/second partial will answer only two questions on the other part of the program in the written exam. 

Syllabus 

Topics and  Book Chapters. Slides and additional material are available on Classroom. 

1.  Overview of Algorithm Analysis Kleinberg and Tardos, Ch. 2.1 - 2.4 

2.  Stable Matching Kleinberg and Tardos, Ch. 1.1, 1.2 

3. Network Flow: Ford and Fulkerson, Capacity Scaling, Shortest Augmenting Paths Kleinberg and Tardos, Ch. 7.1, 7.2, 7.3 

4. Perfect Matching, Circulations, Improved algorithm for bipartite matching (Ascending Price Matching, Hopcroft-Karp) Kleinberg and Tardos, Ch. 1.1, 7.5, 7.7 

5. Greedy Algorithms 

6. Dynamic Programming Kleinberg and Tardos, Ch. 4.1, 4.4, 6.1, 6.2, 6.4,  6.4, 6.8 

7. Basics of complexity and NP-completeness

8. Lecture 8 Basics of approximation algorithms Reference [4], Chapters 1 and 3 

9. Basics of approximation algorithms Reference [4], Chapters 2.1, 8.1, 8.2 

10. Linear Programming based approximation algorithms Reference [4], Chapters 12 

11. Basics of Randomized Algorithms Reference [5], Chapter 5 

Book of the course: 

We follow when possible the book 

[1] J. Kleinberg and E. Tardos, Algorithm Design. Addison Wesley, Pearson Education, 2005. 

Additional material on the book can be found here: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/

Additional References:

I. Matching Algorithms and Flows: Bipartite Matching, Ford and Fulkerson algorithm and Edmonds-Karp algorithm

[2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms (33d ed.), 2011. MIT Press.

II. Approximation Algorithms: 

[3] David Williamson and David Shmoys, The Design of Approximation Algorithms, Cambridge, 2011. A copy of the book can be found 

here

[4] Vijay Vazirani, Approximation Algorithms, Springer 2001.