Advanced Algorithms (Spring 2019)

Course Description

The goal of this course is to introduce classic tools used in the design of approximation algorithms like linear programming and positive semi-definite programming. We will emphasis on rigorous analysis of the performance of approximation algorithms. Moreover, we plan to introduce some modern topics including spectral algorithms and the Markov chain Monte Carlo method.

General Information

Instructor:

Chihao Zhang

Time:

Monday
2:00pm - 3:40pm

Location:

DongXiaYuan (东下院) 202

Office Hour:

Monday
7:00pm - 9:00pm
School of Software (软件学院) 1402-2

News

  • [Apr 19] Notes of Lecture 8 posted.
  • [Apr 15] The second homework has been posted, due on Labour Day.
  • [Apr 08] Notes of Lecture 7 posted.
  • [Apr 06] Notes of Lecture 6 posted.
  • [Mar 30] Notes of Lecture 5 posted. Thanks Mr. LI Muyang for pointing out a typo in the notes of Lecture 2.
  • [Mar 24] Notes of Lecture 4 posted. Notes of Lecture 3 updated.
  • [Mar 18] The first homework has been posted, due on Fool's Day.
  • Lecture Notes

    [Feb 25][notes][slides] MaxSAT, linear programming rounding
    [Mar 04][notes][slides] MaxSAT cont'd, integrality gap, minimum label s-t cut
    [Mar 11][notes][slides] LP for MaxCut, integrality gap for MaxCut LP, positive semi-definite programming
    [Mar 18][notes][slides] Goemans-Williamson rounding, binary quadratic programming, correlation clustering
    [Mar 25][notes][slides] introduction to graph spectrum, Laplacian, Cheeger's inequality
    [Apr 01][notes][slides] proof of Cheeger's inequality
    [Apr 08][notes][slides] sparsest cut, Leighton-Rao relaxation, multicommodity flow, metric embedding
    [Apr 15][notes][slides] proof of Bourgain's metric embedding theorem

    Assignments

    [homework 1][due: Apr 01]
    [homework 2][due: May 01]