[Dec 21] Assignment 3 is out, due on Jan. 9 [Nov 10] Assignment 2 is out, due on Nov. 29. [Oct 11] Assignment 1 is out, due on Oct. 25. SJTU students can find the assignment on Canvas.
Lecture Notes
[Dec 20][slides][handout] Sparsification via effective resistance [Dec 13][slides][handout] Electrical network (cont'd), Approximating effective resistance [Dec 06][slides][handout] Random walk (cont'd), Hitting time, Cover time, Electrical network (See the note and the book) [Nov 29][slides][handout] Graph Laplacian, Courant-Fischer theorem, Random walk [Nov 22][slides][handout] Approximate matrix multiplication; Graph spectrum [Nov 15][slides][handout] Yao's lemma; Lower bound for connectivity; Lower bound for 0-norm [Nov 08][slides][handout] Communication complexity; Disjointness; Lower bound for streaming algorithms [Nov 01][slides][handout] Shortest path; Maximum matchings; Counting triangles [Oct 25][slides][handout] Johnson-Lindenstrauss lemma; p-stable distribution; Graph stream [Oct 18][slides][handout] Count-Min; AMS estimator for frequency moments; Tug-of-War estimator [Oct 11][slides][handout] BJKST algorithm; Frequency estimation; Misra-Gries; Count Sketch [Sep 29][slides][handout] Strongly 2-universal family of Hash functions; AMS algorithm for counting distinct elements [Sep 27][slides][handout] Concentration inequalities; Universal Hash function family [Sep 20][slides][handout] Streaming model, Morris algorithm