Advanced Algorithms (Spring 2020)

Course Description

The course is mainly about the use of random coins to help designing and analyzing algorithms.

General Information


Chihao Zhang


10:00am - 11:40am


The course is taught online
due to COVID-19

Office Hour:

Online via Wechat or
Canvas forum.


[Jun 10] Assignment 6 is out, due on June 22.
[May 20] Assignment 5 is out, due on June 1.
[Apr 30] Assignment 4 is out, due on May 18.
[Apr 14] Assignment 3 is out, due on Apr. 27.
[Mar 24] Assignment 2 is out, due on Apr. 13.
[Mar 09] Assignment 1 is out, due on Mar. 23.

Lecture Notes

[Jun 15][notes][slides][handout] Canonical paths, Sampling matchings
[Jun 08][notes][slides][handout] Sampling Proper Colorings, Edge Expansion, Cheeger's Inequality
[Jun 01][notes][slides][handout] Coupling, Mixing Time, Relaxation Time
[May 25][notes][slides][handout] Fundamental Theorem of Markov Chains, Spectral Decomposition Theorem
[May 18][notes][slides][handout] Partial Rejection Sampling for Independent Sets
[May 11][notes][slides][handout] Sampling, Rejection sampling, Counting DNF
[Apr 28][notes][slides][handout] Moser-Tardos' witness tree proof of Lovász local lemma
[Apr 27][notes][slides][handout] Lovász local lemma
[Apr 20][notes][slides][handout] The Probabilistic Method, Max Cut, Max Sat, Linear Programming Relaxation
[Apr 13][notes][slides][handout] Optional Stopping Theorem
[Mar 30][notes][slides][handout] Martingale, Azuma-Hoeffding, Doob's Martingale
[Mar 23][notes][slides][handout] Chernoff Bound, Hoeffding Inequality, Multi-Armed Bandits, UCB
[Mar 16][notes][slides][handout] Balls-into-Bins, Markov Inequality, Chebyshev's Inequality
[Mar 09][notes][slides][handout] Linearity of Expectation, Coupon Collector, Karp-Upfal-Wigderson Inequality
[Mar 02][notes][slides][handout] Polynomial Identity Testing, Schwartz-Zippel Theorem, Karger's Min-cut Algorithm