Sep 8: Intro, approximate counting (Morrisâ€™ algorithm).

Lecture 1 slides. Scribe notes: [pdf], and [original tex].

Sep 10: Chernoff/Hoeffding bounds. Distinct elements count. Impossibility results.

Lecture 2 slides. Scribe notes (draft): [pdf], and [original tex].

Sep 15: Frequency moments (F_2 from Alon-Matias-Szegedy), heavy hitters (CountMin/CountSketch).

Lecture 3 slides: in pptx and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- lecture 5 from Jelani's class below.

Sep 17: CountSketch, Precision Sampling (for High frequency moments).

Lecture 4 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

Sep 21 (Mon):

Sep 22: High moments via Precision Sampling, Streaming for Graphs.

Lecture 5 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- blog post on p-moments via Precision Sampling.
- lecture 6 from Jelani Nelson's class.
- Graph Stream Algorithms: a Survey, by Andrew McGregor.

Sep 24: Streaming for Graphs: counting triangles, dynamic graphs.

Lecture 6 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- counting triangles: Graph Stream Algorithms: a Survey, by Andrew McGregor
- dynamic graphs: lecture 6 from Jelani Nelson's class.

Sep 29: dynamic graph algorithms, dimension reduction.

Lecture 7 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- dynamic graphs: lecture 6 from Jelani Nelson's class.

Oct 1: dimension reduction, p-stable distributions.

Lecture 8 slides and in pdf. Scribes (draft): [pdf] and [tex]

related material:

- dimension reduction: Lecture 9 from Jelani Nelson's class.
- Lecture 5 from Piotr Indyk and Ronitt Rubinfeld's class.
- proof of JL: see Piotr Indyk's writeup.

Oct 6: fast dimension reduction.

Lecture 9 slides and in pdf. Scribes (draft): [pdf] and [tex].

Related material

- Lecture 12 from Jelani Nelson's class.

Oct 7:

Oct 8: sketching, nearest neighbor search.

Lecture 10 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- for sketch on Hamming distance, see the original KOR paper (may be technically hard to read).

Oct 13: NNS: Locality Sensitive Hashing.

Lecture 11 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- LSH: see this book chapter, or wiki webpage.

Oct 15: NNS: more LSH, data-dependent hashing.

Lecture 12 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- for data-dependent hashing, see this blog post or the full article (may be technically hard to read).

Oct 20: compressed sensing from JL

- lecture notes
- Lecture 16 from Jelani Nelson's class
- A Mathematical Introduction to Compressed Sensing by Foucart, Rahut
- RIP from JL

Oct 22: More applications of dimension reduction: approximate matrix multiplication, least squares regression.

Scribes (draft): [pdf] and [tex].

Resources:

- lecture 13, and lecture 14 from Jelani Nelson's class.

Oct 27: Least Squares Regression, metric embeddings.

Lecture 15 slides and in pdf.

Resources:

- LSR: lecture 14 from Jelani Nelson's class.
- metric embeddings: see lecture 1 and 2 from Goemans' class at MIT.

Oct 29: Earth-Mover Distance.

Lecture 16 slides and in pdf. Scribes (draft): [pdf] and [tex].

Related material:

- see the paper by Indyk and Thaper.

Nov 6: sublinear time.

Lecture 17 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- lecture 7 from Paul Beame's class at UW.

Nov 10: Distribution testing, monotonicity, and testing connectivity in graphs.

Lecture 18 slides and in pdf. Scribes (draft): [pdf] and [tex].

related material:

- paper by Valiant and Valiant (see section 3).
- lecture 15 of Paul Beame's class.

Nov 12: Sublinear algorithms in graphs.

Scribes (draft): [pdf] and [tex].

related material:

- lecture 15 of Paul Beame's class.
- lecture 12 (notes) from the Piotr Indyk and Ronitt Rubinfeld's class.

Nov 17: Sublinear Graph Approximation Algorithms (by Krzysztof Onak).

Lecture 20 slides.

Nov 19: Testing functions: linearity testing.

Lecture 21 scribes: [pdf] and [tex].

related material:

- lecture 8 from the Piotr Indyk and Ronitt Rubinfeld's class.

Nov 24: Learning Fourier coefficients.

Lecture 22 slides and in pdf.

Nov 26:

Dec 1:

MapReduce model, and algorithms for MapReduce model.

Guest lecture by Sergei Vassilvitskii.

Dec 3: MapReduce algorithms.

Lecture 24 slides and in pdf. Scribes: [pdf] and [tex].

Dec 8,10,11: project presentations. Sign-up here.

Dec 14:

Lecture notes for similar classes at other universities (a selection of):

- Algorithms for Big Data (F13) , by Jelani Nelson (Harvard)
- Algorithms for Big Data, by Chandra Chekuri (UIUC)
- Sublinear Algorithms, by Piotr Indyk and Ronitt Rubinfeld (MIT)
- Sublinear and Streaming Algorithms, by Paul Beame (UW)

- Data Stream Algorithms, by Amit Chakrabarti.
- Graph Stream Algorithms: a Survey, by Andrew McGregor.