Algorithms for Big Data (Fall 2019)

General Information


Chihao Zhang


12:55 - 15:40


DongShangYuan (东上院) 107

Office Hour:

6:00pm - 8:00pm
School of Software (软件学院) 1402-2


The main references of this course are lecture notes from following courses:

  • Data Stream Algorithms
  • Algorithms for Big Data
  • Algorithmic Techniques for Big Data
  • Algorithms for Massive Data
  • Sketching Algorithms for Big Data
  • Spectral and Algebraic Graph Theory
  • News

    [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