Algorithm Design 2020/2021

Algorithm Design 2020/2021

Master's degree in Engineering of Computer Science

Lectures will start on October 6th

Schedule of lessons:

Tuesday, 08:00 - 11:00, Lecture Room 205, Building Marco Polo, Circonvallazione Tiburtina, 4

Friday, 11:00 - 13:00, Lecture Room 205, Building Marco Polo, Circonvallazione Tiburtina, 4

All lectures will be broadcasted on zoom at

https://uniroma1.zoom.us/j/83916126820?pwd=UXY0c0VZZGoyUk9zSVNSQnRWWVBTQT09

Instructors:

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

Dr. Philip Lazos lazos -- at -- diag.uniroma1.it

Dr. Rebecca Reiffenhauser rebeccar -- at -- diag.uniroma1.it

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

For the Algorithm Design Piazza site, enroll at AD 1920 on Piazza piazza.com/uniroma1.it/fall2020/ad20202021

There are two possibilities for passing the exam:

1) The first and most advised one is to submit the two Homeworks before deadline. The homeworks will be discussed during the exam.

2) The second one is to answer two questions on the topics of the first homework (Fundamental design methods and Poly-time algorithms) and three questions on the topics of the second homework (Approximation of hard problems and Computational game theory) during in the written exam.

The student that either fails or does not submit the only first/second homework will answer only two/three questions in the written exam.

Syllabus

Lecture Date Topic Book chapters Slides

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

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

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

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

5 Lecture 5 Greedy Algorithms slides

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

7 Lecture 7 Basics of complexity and NP-completeness

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

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

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

11 Lecture 11 Basics of Randomized Algorithms Reference [5], Chapter 5 slides

12 LEcture 12 Introduction to Game Theory and Equilibria Computation Lecture Notes

13 Lecture 13 Computing Equilibria in Zero-Sum Games and Efficiency of Equilibria Lecture Notes

14 Lecture 14 Selfish Routing and Price of Anarchy See Lecture Notes of Lecture 14 and Exercises, Section 2

Book of the course:

We follow as closely as 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.

The book can be found here

[5] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998.

Chapters available online:

* Chapter 2: Design Techniques for Approximation Algorithms

* Capitolo 3: Approximation Classes

* Capitolo 4: Input-Dependent and Asymptotic Approximation

* Capitolo 5: Approximation through Randomization