Theoretical Computer Science
- Tuesday, 09:00 - 11:45, Room B2, Via Ariosto
- Thursday, 12:00 - 13:30, Room B2, Via Ariosto
- Prof. Stefano Leonardi
- Dr. Marek Adamczyk
- Dr. Erik Jan van Leeuwen
Office Hour: after the lecture of Tuesday or upon appointment at email@example.com
Tutor in Italiano: Dr.ssa Donatella Firmani. Riceve il Mercoledi' dalle 17:00 alle 19:00. email: firstname.lastname@example.org
Prof. Alberto Marchetti-Spaccamela will be in charge of the exam sessions of July ans September.
Please, refer to his record on Infostud if you like to attend the exam of Theoretical Computer Science.
Prof. Stefano Leonardi will visit Google labs till September. Please send email or refer to i) Prof. Alberto Marchetti Spaccamela, ii) Tutors Marek Adamczyk and Donatella Firmani for office hour.
- Lecture 1. Lecture Overview & Introduction to Complexity. lecture1.pdf. Reference .
- Lecture 2. Network flow: Ford and Fulkerson, Max Flow - Min Cut. From Kleinberg and Tardos book on Algorithm Design: 07maxflow.pdf. Slides also available here. Exercises on Max-Flow Circulations.pdf. Reference , cap 7.
- Lecture 3. Matching in Bipartite Graphs and Marriage Theorem. From Kleinberg and Tardos book on Algorithm Design: 07maxflow-applications.pdf. Stable Matching: stablematching.pdf. Reference , Cap. 7.
- Applications of Network flow. From Kleinberg and Tardos book on Algorithm Design: 07maxflow-applications.pdf. Exercises on Network Flow maxflow-example.pdf Reference , Cap. 7.
- Greedy Algorithms: Interval Scheduling, Interval Partitioning. From Kleinberg and Tardos book on Algorithm Design: 04greed.pdf. Reference , Cap. 4.
- Dynamic Programming: Weighted Interval scheduling, Knapsack, Bellman-Ford. From Kleinberg and Tardos book on Algorithm Design: 06dynamic-programming.pdf. Excercises on Dynamic Programming: dp-exercises.pdf . Reference , Cap. 6.
- Basic concepts of approximation algorithms: simple examples, ptas, LP-based approximation (4 h) basicsapx.pdf LPapprox.pdf. Reference .
- Primal-Dual Approximation Algorithms for Network Design Problems: Facility location and Steiner tree. Slides from the lecture: primaldual.pdf. See also: FacilityLocation.pdf Steiner trees.pdf. Reference . Exercises on Steiner trees: http://www.dis.uniroma1.it/~adamczyk/files/classolutions.pdf classolutions.pdf
- Randomized approximation algorithms: randrounding.pdf. Excercises and Extensions: randroundingexcercises.pdf. Reference .
- Computational Game Theory: games
- Efficiency of Equilibria and Price of Anarchy priceofanarchy
First Homework: Homework1.pdf
(to be done alone or in pairs)
Solutions to be mailed (pdf format) to email@example.com by Tuesday, December 11th, 2012 (Deadline Extended).
Examples for Exercises 1 and 3: examples-homework1.pdf
First Homework: homework2.pdf
(to be done alone or in pairs)
Solutions to be mailed (pdf format) to firstname.lastname@example.org by Tuesday, January 12th, 2012.
Comments and exercises from last classes that are of interest for the second homework comments homework2
Results of the exam of 25/01/2013 ESAMI25-01-2013.pdf
Results of the exam of 18/02/2013 ESAMITCS18-02-2013.pdf
Results of the exam of 10/06/2013 ESAMITCS10-06-2013.pdf
Testi di Esame
Testi di Esame 2013
Theoretical Computer Science - References
I. Complexity classes:
 D. Bovet, P. Crescenzi, Introduction to the Theory of Complexity, Prentice-Hall, 1994
The authors have made available for free the whole book in PDF format. You can access it from the author's webpage.
II. Matching Algorithms and Flows: Bipartite Matching, Ford and Fulkerson algorithm and Edmonds-Karp algorithm
 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.
Matching in General Graphs
 by L. Lovasz, M. D. Plummer, Matching Theory, North-Holland Mathematics Studies 121.
 J. Kleinberg and E. Tardos, Algorithm Design. Addison Wesley, Pearson Education, 2005.
III. Approximation Algorithms:
 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998.
Chapters available online:
 V. Vazirani, Approximation Algorithms, Springer-Verlag, 1999.