Scribing:

Due by midnight next day after lecture. You have to use the following LaTeX template: scribe.tex. For a short introduction to LaTeX, see this mini-course. The scribed lecture will be posted immediately after it is received so that the rest of the class can use it before the following lecture. The staff will review the scribe, and, if necessary, the scriber(s) will be asked to rectify the lecture.

Schedule & Resources:

Jan 18: intro, approximate counting, Morris algorithm.
Lecture 1 scribe notes.
Other resources:

Jan 23: approximate counting (cont). Hashing: universal and perfect.
Lecture 2 scribes.
Resources:

Jan 25: Hashing: power of 2 choices.
Lecture 3 scribes.
[HW1 assigned]. Resources:


Jan 30: Sketching: Distinct Elements Count. Impossibility results.
Lecture 4 scribes.
Resources:

Feb 1: Heavy Hitters, countMin algorithm.
Lecture 5 scribes.
Resources:

Feb 6: Faster countMin, frequency moments.
Lecture 6 scribes.
Resources:

Feb 8: Dimension reduction, p-stable distributions.
Lecture 7 scribes.
[PS1 due, HW2 out]
Resources:

Feb 13: Nearest neighbor search: introduction.
Lecture 8 scribes.
Resources:

Feb 15: Nearest neighbor search: Locality Sensitive Hashing.
Lecture 9 scribes.
Resources:

Feb 20: [optional lecture]: advanced NNS algorithms.
Lecture slides: in pdf format and in pptx format.
Scribe notes.
Resources:

Feb 22: Graph algorithms.
Lecture 10 scribes.
[PS2 due, HW3 out]
Resources:

Feb 27: Graph algorithms.
Lecture 11 scribes.
Resources:

Mar 1: Graph algorithms.
Lecture 12 scribes.
Resources:

Mar 6: Spectral graph algorithms: adjacency matrix, random walks, eigenvalues, Rayleigh quotient.
Lecture 13 scribes.
Resources:

Mar 8: Spectral graph algorithms: connections between eigenvalues and graph properties, top eigenvalues.
Lecture 14 scribes.
[PS3 due]
Resources:

[SB: Mar 13,15 SPRING BREAK]

Mar 20: Spectral graph algorithms: Laplacian graphs, drawing, cuts in graphs.
Lecture 15 scribes.
Resources:


Mar 22: Spectral graph algorithms: Cheeger inequality and 2nd eigenvalue.
Lecture 16 scribes.
[project proposal due, HW4 out]
Resources:

Mar 27: Linear programming: introduction, linear system of equations.
Lecture 17 scribes.
Resources:

Mar 29: Linear programming: duality.
Lecture 18 scribes.
Resources:

Apr 3: Linear programming: strong duality.
Lecture 19 scribes.
Resources:

Apr 5: Linear programming: simplex and ellipsoid algorithms.
Lecture 20 scribes.
Resources:
[PS4 due]

Apr 10: Linear programming: gradient descent.
Lecture 21 scribes.
Resources:

Apr 12: Linear programming: Newton's method, interior point algorithms.
Lecture 22 scribes.
Resources:

Apr 17: Linear programming: multiplicative weights update.
Lecture 23 scribes.
Resources:
[project report (2) due, HW5 out]

Apr 19: Large-scale models: external memory.
Lecture 24 scribes.
Resources:

Apr 24: Large-scale models: cache-oblivious, parallel algorithms.
Lecture 25 scribes.
Resources:
  • cache-oblivious algorithms: E. Demaine's lecture notes (L7).
  • parallel algorithms: lecture 27 from D. Karger and A. Madry's class.

Apr 26: Parallel algorithms (MapReduce/MPC). Class recap.
Resources:
  • parallel algorithms: lecture 27 from D. Karger and A. Madry's class.
  • parallel connectivity: see this lecture (pdf) from G. Yaroslavtsev's class.


May 1: lecture by Erik Waingarten on NNS under l_infty and metric embeddings.
[HW5 due]

May 12: final projects due.