Algorithm Design 2023/2024

Algorithm Design 2023/2024

Master's degree in Engineering of Computer Science

Lectures will start on September 26th

Schedule of lessons: 

Tuesday, 10:00 - 12:00, Room 29, San Pietro in Vincoli 

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

Instructors: 

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

Prof. Federico Fusco   fuscof--at--diag.uniroma1.it 

Office Hour: after the lecture of Tuesday 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 on November 17th and December 19th. 

2) The second is attending 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 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.