Advanced Algorithms (Spring 2020)

Course Description

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

General Information

Instructor:

Chihao Zhang

Time:

Monday
10:00am - 11:40pm

Location:

The course is taught online
due to COVID-19

Office Hour:

Online via Wechat or
Canvas forum.

News

[Mar 24] Assignment 2 is out, due on Apr. 13.
[Mar 09] Assignment 1 is out, due on Mar. 23.

Lecture Notes

[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

Assignments