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:

Oct 22: More applications of dimension reduction: approximate matrix multiplication, least squares regression. Scribes (draft): [pdf] and [tex]. Resources:

Nov 10: Distribution testing, monotonicity, and testing connectivity in graphs. Lecture 18 slides and in pdf. Scribes (draft): [pdf] and [tex]. related material:

Schedule: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:

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):

[PS1 due].Sep 22: High moments via Precision Sampling, Streaming for Graphs.

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

related material:

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

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

related material:

Sep 29: dynamic graph algorithms, dimension reduction.

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

related material:

Oct 1: dimension reduction, p-stable distributions.

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

related material:

Oct 6: fast dimension reduction.

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

Related material

Oct 7:

[PS2 due].Oct 8: sketching, nearest neighbor search.

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

related material:

Oct 13: NNS: Locality Sensitive Hashing.

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

related material:

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

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

related material:

Oct 20: compressed sensing from JL

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

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

Resources:

Oct 27: Least Squares Regression, metric embeddings.

Lecture 15 slides and in pdf.

Resources:

Oct 29: Earth-Mover Distance.

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

Related material:

Nov 6: sublinear time.

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

related material:

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

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

related material:

Nov 12: Sublinear algorithms in graphs.

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

related material:

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:

Nov 24: Learning Fourier coefficients.

Lecture 22 slides and in pdf.

Nov 26:

.NO CLASSDec 1:

MapReduce model, and algorithms for MapReduce model.

Guest lecture by Sergei Vassilvitskii.

.[PS5 due]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:

.[projects due]Study resources: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)

Surveys, expository articles: