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


Chihao Zhang


2:00pm - 3:40pm


DongXiaYuan (东下院) 202

Office Hour:

7:00pm - 9:00pm
School of Software (软件学院) 1402-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


    [homework 1][due: Apr 01]