Stefano Leonardi

Home :: Publications :: Login
Theoretical Computer Science

Schedule:


Instructors:



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.



  1. Lecture 1. Lecture Overview & Introduction to Complexity. lecture1.pdf. Reference [1].
  2. 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 [4], cap 7.
  3. 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 [4], Cap. 7.
  4. Applications of Network flow. From Kleinberg and Tardos book on Algorithm Design: 07maxflow-applications.pdf. Exercises on Network Flow maxflow-example.pdf Reference [4], Cap. 7.
  5. Greedy Algorithms: Interval Scheduling, Interval Partitioning. From Kleinberg and Tardos book on Algorithm Design: 04greed.pdf. Reference [4], Cap. 4.
  6. 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 [4], Cap. 6.
  7. Basic concepts of approximation algorithms: simple examples, ptas, LP-based approximation (4 h) basicsapx.pdf LPapprox.pdf. Reference [1].
  8. 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 [6]. Exercises on Steiner trees: http://www.dis.uniroma1.it/~adamczyk/files/classolutions.pdf classolutions.pdf
  9. Randomized approximation algorithms: randrounding.pdf. Excercises and Extensions: randroundingexcercises.pdf. Reference [6].
  10. Computational Game Theory: games
  11. Efficiency of Equilibria and Price of Anarchy priceofanarchy





Homework1

First Homework: Homework1.pdf

(to be done alone or in pairs)

Solutions to be mailed (pdf format) to adamczyk@dis.uniroma1.it by Tuesday, December 11th, 2012 (Deadline Extended).

Examples for Exercises 1 and 3: examples-homework1.pdf



Homework2

First Homework: homework2.pdf

(to be done alone or in pairs)

Solutions to be mailed (pdf format) to adamczyk@dis.uniroma1.it 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:

[1] 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

[2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.

Matching in General Graphs

[3] by L. Lovasz, M. D. Plummer, Matching Theory, North-Holland Mathematics Studies 121.

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

III. Approximation Algorithms:

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


[6] V. Vazirani, Approximation Algorithms, Springer-Verlag, 1999.
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.6
Page was generated in 0.4395 seconds