Theoretical Computer Science

Computer engineering (Master degree)

2011-2012, 6  credits


Prof.  Alberto Marchetti Spaccamela



Syllabus

PART  I 
1.  Overview & Introduction to Complexity.  
2.  Matching Algorithms: matching in bipartite graphs, augmenting paths, Edmonds and Karp algorithm, matching in general graphs. 
3. Max Flow problem: problem formulation, primal dual. Ford and Fulkerson algorithm
4. Applications of Network flow from Kleinberg and Tardos book on Algorithm Design.
    Bipartite matching and flow, edge-disjoint paths, vertex-disjoint paths, Flow circulation, Flow circulation with lower bounds. A lecture from this chapter is available here
5. Dynamic programming

Bibliographic references
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

P. Sankoski: slides,  
Slides and reference for dynamic programming 
Exercises-1


PART II 
1. Basic concepts of approximation algorithms: simple examples, greedy, ptas, LP-based approximation
2. Negative results for approxiability, approximation classes, pseudo polynomial algorithms, strong NP-hard problems
3.  Min-max relations for Min Cut - Max Flow, Primal-Dual Approximation Algorithms for Network Design Problems: Facility location and Steiner tree: FacilityLocation.pdf,  Steiner trees.pdf
4. Randomized approximation algorithms: randrounding.pdf
5. Approximation algorithms for other specific problems: scheduling, TSP, vertex cover, max and min Knapsack, max satisfiability, set cover.

Bibliographic references
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998

We have covered material form the following chapters  (downloadable on-line, thanks to the publisher):
    * Chapter 2: Design Techniques for Approximation Algorithms
    * Chapter 3: Approximation Classes
    * Chapter 4: Input-Dependent and Asymptotic Approximation
    * Chapter 5: Approximation through Randomization
    * References

A. Marchetti-Spaccamela:  Introduction to approximate algorithms
S. Leonardi: slides, 
Exercises-2


PART III 
1. Computational Game Theory: pure and mixed Nash equilibria, examples
2. Compuational learning and relation with game theory

Bibliographic references
V.Bonifaci:Introduction to game-theory
M.Balcan: slides on computational learning
Exercises-3