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.

Overview of Algorithm Analysis Kleinberg and Tardos, Ch. 2.1 - 2.4
Stable Matching Kleinberg and Tardos, Ch. 1.1, 1.2
Network Flow: Ford and Fulkerson, Capacity Scaling, Shortest Augmenting Paths Kleinberg and Tardos, Ch. 7.1, 7.2, 7.3
Perfect Matching, Circulations, Improved algorithm for bipartite matching (Ascending Price Matching, Hopcroft-Karp) Kleinberg and Tardos, Ch. 1.1, 7.5, 7.7
Greedy Algorithms
Dynamic Programming Kleinberg and Tardos, Ch. 4.1, 4.4, 6.1, 6.2, 6.4, 6.4, 6.8
Basics of complexity and NP-completeness
Lecture 8 Basics of approximation algorithms Reference [4], Chapters 1 and 3
Basics of approximation algorithms Reference [4], Chapters 2.1, 8.1, 8.2
Linear Programming based approximation algorithms Reference [4], Chapters 12
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.