Advanced Algorithms

Spring 2011

Institute for Theoretical Computer Science, Institute for Interdisciplinary Sciences, Tsinghua University
Instructor: Periklis A. Papakonstantinou []
Teaching assistants: Wei Hu, Xiaohong Hao
Lectures: Tuesday and Wednesday 1.30-3.05pm
Office hours: Tuesday 12.30-1.30pm (or by appointment), FIT 4-608-7


[May 30] Assignment 5 is posted
[Jun 2] Assignment 6 is posted

Handouts, problem-sets, and links


Discussion forum


Date Topic
Jun 8 Putting everything together: review class
Jun 1 The second streaming approximation algorithm for F_0: tradeoffs between quality of approximation and space
May 31 The proof for the bounds on the first distinct elements approximation algorithm
May 25 Introduction streaming lower bounds via Communication Complexity.
More on approximating the number of distinct elements - applications of hashing to streaming
May 24 Basics of streaming algorithms: approximating the number of distinct elements, frequency moments estimation
May 17 Introduction to streaming and sublinear algorithms.
May 11 Applications of embeddings to algorithm design. The Linial-London-Rabinovitch algorithm for SPARSEST-CUT.
May 10 Proof of Bourgain's theorem for finite metric spaces
May 6 Introduction to Finite Metric Spaces. Bourgain's theorem
Apr 28 Primal-dual approximation algorithms: using LPs without solving them
Apr 27 More on classical approximation algorithms: PTAS & FPTAS, classes of optimization approximation problems
Apr 20 SDP relaxations: the Goemans-Williamson algorithm
Apr 19 An overview of the Ellipsoid Algorithm: correctness and running time. Elements of semi-definite programming
Apr 13 More on the geometry of Linear Programming
Apr 12 The geometry of linear programming: basic feasible solutions, an outline of the Simplex Algorithm
Mar 30 Randomized rounding for the standard Set Cover relation. Derandomizing the obvious Max-k-SAT algorithm using the method of conditional expectations
Mar 29 Two approximation algorithms for Set Cover: standard greedy algorithm, deterministic rounding
Mar 23 An LP-based proof of the max-flow=min-cut theorem. Introduction to randomized rounding.
Mar 22 A geometric proof of the Farkas Lemma
Mar 16 More about LP-duality, Farkas lemma, optimizing over polytopes
Mar 15 Geometry of polytopes, Linear programs, elements of LP-duality, the proof of the LP-duality theorem
Mar 9 The proof of the max-flow min-cut theorem, more about reductions, Vertex Cover, 2-approximation of VC
Mar 8 Flows, cuts, and matchings. Bipartite matching, reductions, examples, introduction to the max-flow min-cut theorem
Mar 2 Optimization problems, introduction to approximation algorithms, greedy approximations of Makespan, on-line algorithms
Mar 1 Linear space sequence alignment - space savings by combining Dynamic Programming and Divide and Conquer
Feb 23 Classical algorithmic paradigms (review material): greedy algorithms and dynamic programming
Feb 22 Introduction, class overview