Lecture Schedule
Much of the material is covered in lecture notes for a previous offering of the course, numbered CS 369G. I will be updating some of these notes as we go along.
In addition, the handwritten notes from the Spring 2020 class can be found at tinyurl.com/cs368notes.
| Date | Topic | Notes |
|---|---|---|
| 3/28 | Counting distinct elements |
|
| 3/30 | Distinct elements cont. |
|
| 4/4 | Lower bounds for distinct elements, Frequency moments, Estimating F_2. |
|
| 4/6 | Johnson-Lindenstrauss Lemma | |
| 4/11 | Lower bound for Euclidean dimension reduction. Estimating F_k, k in (0,2) via stable distributions |
|
| 4/13 | Pseudorandom generator for F_k estimation, k in (0,2) Heavy Hitters (Misra-Gries algorithm) |
|
| 4/18 | Count-Min and Count-Sketch |
|
| 4/20 | L0 sampling |
|
| 4/25 | Connectivity and cuts in the semi-streaming Model |
|
| 4/27 | Graph spanners and intro. to communication complexity | |
| 5/2 | Communication complexity cont. |
|
| 5/4 | Lower bounds and gap hamming | |
| 5/9 | High-dimensional nearest neighbours | |
| 5/11 | L2 subspace embedding and sketching for numerical linear algebra | |
| 5/16 | L2 subspace embedding cont. | |
| 5/18 | MapReduce intro, MST & Filtering | |
| 5/23 | Connected comp. and MST in MapReduce | |
| 5/25 | Introduction to Coresets |