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.30-5.05pm (4x45min)
Office hours: Tuesday 12.30-1.30pm (or by appointment), FIT 4-608-7



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

Handouts, problem-sets, and links

References

Discussion forum



Lectures

Date Topic
Dec 20 Influence. The Goldreich-Levin algorithm.
Learning through spectral concetration.
Wrap-up: 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 Goemans-Williamson algorithm
PTAS and FPTAS
Nov 22 More on LP-relaxations. Rounding techniques. Case-study: SET-COVER.
LP-based algorithms without solving the LP: Primal-dual approximation algorithms
Greedy derandomization via conditional expectations.
Nov 15 The Ellipsoid algorithm: correctness and running time analysis (lecturer: Xiaohong Hao).
An LP-based proof of Max Flow = Min Cut. Introduction to rounding techniques, and a greedy algorithm for SET-COVER.
Nov 8 Elements of the geometry of linear programs. Overview of the Simplex and the Ellipsoid algorithms.
Nov 1 LP-duality: a geometric proof of the LP-duality 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, Edmonds-Karp 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