|
Theoretical Computer Science |
 |
 |
 |
|
Written by Administrator
|
|
Thursday, 08 October 2009 11:27 |
Theoretical Computer Science
Stefano Leonardi
This e-mail address is being protected from spambots. You need JavaScript enabled to view it
Piotr Sankowski
This e-mail address is being protected from spambots. You need JavaScript enabled to view it
Lecture 1: Lecture Overview & Introduction to Complexity
Lecture Slides
Exercises
For additional information please see the following textbook
Lecture 2: Matching Algorithms
Lecture Slides
Exercises
Lecture 3: Intorduction to Approximation Algorithms
Lecture Slides
Lecture 4: Flow Algorithms
Lecture Slides
The animations from the lecture (stil in original language)
Zasd_ilustr_b.swf Zasd_ilustr_e.swf Zasd_ilustr_l.swf Zasd_ilustr_p.swf Zasd_ilustr_q.swf Zasd_ilustr_r.swf
Lecture 5: FFT and Polynomial Algorithms
Lecture Slides
ilustr_u.swf ilustr_a.swf
Lecture 6: Design of Approximation Algorithm Based on Mathematical Programming Techniques
Lecture Slides
Lecture 7: Min-Max Relations
Lecture Slides
Lecture 8: Randomized Rounding
Lecture Slides
Lecture 9: Primal Dual Algorithms for Network Design
Lecture Slides
Lecture 10: Randomized Rounding
Lecture Slides, Exercises
Lecture 11: Computational Game Theory
Lecture Slides |
|
Last Updated on Monday, 10 May 2010 12:32 |
|
Theoretical Computer Science - References |
|
|
|
|
Written by Administrator
|
|
Thursday, 22 October 2009 17:24 |
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 or from our local copy.
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
Dinic Algorithm
[4] Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". in Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman. Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218?240. ISBN 978-3540328803. http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf.
[5] B. H. Korte, Jens Vygen (2008). "8.4 Blocking Flows and Fujishige's Algorithm". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174?176
III. FFT and polynomial algorithms:
[6] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.
IV. Approximation algorithms:
[7] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998
Here are some of the chapters of the book:
Linear programming based techniques for approximation algorithms can be found here. The lectures on this topic are based on Chapters 12, 13, 14, 15, 16, 20, 22, 24.
[8] V. Vazirani, Approximation Algorithms, Springer, 2003
|
|
Last Updated on Friday, 30 October 2009 12:26 |
|
|
Theoretical Computer Science - Syllabus |
|
|
|
|
Written by Administrator
|
|
Friday, 30 October 2009 12:23 |
Theoretical Computer Science - Syllabus
A.A. 2009/2010
I. Complexity classes: Complexity classes and their basic properties. The classes P, NP, PSPACE. Reductions and completeness in complexity classes.
NP-complete problems.
II. Matching and Flows Algorithms: Bipartite Matching. Flow algorithms Ford and Fulkerson algorithm. Edmonds-Karp algorithm. Dinic Algorithm. Matching in General Graphs.
III. Fast Fourier Transfrom, multiplication, division and n-point evaluation.
IV. BAsics on Approximation Algorithms: Basic concepts in approximation algorithms. Introduction to approximation algorithms. TSP: approximability and inapproximability. Classes of approximability.
V. Greedy algorithms: Vertex cover, Set cover and knapsack. Scheduling: Graham algorithm. Approximation schemes: Knapsack.
VI. LP-based approximation algorithms: LP-rounding approximation algorithms. LP relaxation of combinatorial optimization problems. LP rounding: Vertex cover. Integrality gap.
VII. The Primal-dual based approximation algorithms: LP-duality. Min-max relations: max-flow, min cut theorem. Primal-dual algorithms: Vertex-cover. Dual-fitting analysis of Greedy Set-cover.
VIII. Network Design Problems: Facility location. Steiner trees and Steiner forest.
IX. Randomized rounding: LP relaxation and randomized rounding. Set cover. Max-cut and Max Sat.
X. Exercises and Extensions: Total unimodularity of min-cut. f-approximation for Set-cover. Half-integrality of Vertex cover. O(log n) approximation of non-metric facility location. Price-collecting steiner tree. Set multi-cover. De-randomization of Randomized Approximation Algorithms.
XI. Algorithmic Game Theory: games and solution concepts. Normal form games. Dominating strategy solutions. Pure and mixed Nash equilibria.
Existence and computation of equilibria. An example: the bandwidth sharing game. Zero-sum games and linear programming. Mixed Nash equilibria in arbitrary games.
XII. Inefficiency of equilibria: Price of anarchy and price of stability. Selfish routing: existence of equilibrium flows. Selfish routing: bounds on the price of anarchy.
References:
[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.
[2] by L. Lovasz, M. D. Plummer, Matching Theory, North-Holland Mathematics Studies 121
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998
[4] V. Vazirani, Approximation Algorithms, Springer, 2003.
[5] N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, Algorithmic Game Theory, Cambridge University Press, 2007.
|
|
Last Updated on Friday, 30 October 2009 12:24 |
|