Advanced Algorithms
Fall 2011
Institute for Theoretical Computer Science, Institute for Interdisciplinary Sciences, Tsinghua University

Instructor: Periklis A. Papakonstantinou [papakons@tsinghua.edu.cn] 
Teaching assistants: Xiaohong Hao, Guanyu Wang 
Lectures: Tuesday 1.305.05pm (4x45min) 
Office hours: Tuesday 12.301.30pm (or by appointment), FIT 46087 
News
[Dec 28] 
The final exam will be held on January 2nd, at 9am (lasts for 4 hours)

[Dec 14] 
The second assignment is posted


Exam & Tests table
 Final Exam: Jan 2, starts: 9am (4 hours), Tsinghua School for Yao Class (112,113)
 Test #4: Dec 24, starts: 9am (100 minutes), at 6A115
 Test #3: Dec 3, starts: 9am (100 minutes), 6A115
 Test #2: Nov 5, starts: 9am (100 minutes), at 6A115
 Test #1: Oct 11, starts: 1.30pm (100 minutes), at 6B202
Lectures
Date  Topic 
Dec 20 
Influence. The GoldreichLevin algorithm.
Learning through spectral concetration.
Wrapup: what was this class about? 
Dec 13 
The BLR test works. Hastad's test on dictatorship testing. Introduction to PAC learning

Dec 6 
Introduction to property testing. Basics of Fourier Analysis on the boolean cube. An overview of the BLR test.

Nov 29 
The GoemansWilliamson algorithm
PTAS and FPTAS

Nov 22 
More on LPrelaxations. Rounding techniques. Casestudy: SETCOVER.
LPbased algorithms without solving the LP: Primaldual approximation algorithms
Greedy derandomization via conditional expectations.

Nov 15 
The Ellipsoid algorithm: correctness and running time analysis (lecturer: Xiaohong Hao).
An LPbased proof of Max Flow = Min Cut. Introduction to rounding techniques, and a greedy algorithm for SETCOVER. 
Nov 8 
Elements of the geometry of linear programs. Overview of the Simplex and the Ellipsoid algorithms. 
Nov 1 
LPduality: a geometric proof of the LPduality theorem, Farkas Lemma 
Oct 25 
Tutorial class: review of Linear Algebra and Probability theory, introduction to the Probabilistic Method 
Oct 18 
Elements of theory of polytopes. Forms of Linear Programs. 
Oct 11 (half class) 
Introduction to approximation algorithms 
Sep 27 
Revision: Matchings and Flows: proof of the duality theorem for flows and cuts, EdmondsKarp algorithm and analysis 
Sep 20 
Revision: Dynamic Programming  how to do (some) DP algorithms in small space  space efficient implementation for Sequence Alignment 
Sep 13 
Introduction, class overview
Revision: Greedy Algorithms, proofs of correctness, time and space resources 
