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

  • [May 27] The third homework has been posted, due on June 17.
  • [May 21] Notes of Lecture 12 posted.
  • [May 13] Notes of Lecture 11 posted.
  • [May 03] Notes of Lecture 10 posted.
  • [Apr 27] Notes of Lecture 9 posted.
  • [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
    [Apr 22][notes][slides] introduction to Markov chains, convergence theorem
    [Apr 29][notes][slides] Monte Carlo algorithms, #DNF, Metropolis algorithm
    [May 06][notes][slides] coupling, sampling proper colorings
    [May 13][notes][slides] eigenvalues of Markov chains, relaxation time, product chains
    [May 20][notes][slides] canonical paths, sampling matchings
    [May 27][notes][slides] Lovász local lemma, Moser's entropy compression argument
    [Jun 03][notes][slides] asymmetric Lovász local lemma, Moser-Tardos' witness tree

    Assignments

    [homework 1][due: Apr 01]
    [homework 2][due: May 01]
    [homework 3][due: June 17]