Instructor: R. Teal Witter. Please call me Teal.
Class Times: We meet Monday, Tuesday, Wednesday, and Thursday in 75 Shannon St Room 202. The lecture is from 10am to noon and the discussion is from 2 to 3pm.
Office Hours: I will hold office hours in 75 Shannon St Room 221 from 3 to 4pm.
Participation: I expect you to engage in class, ask questions, and make connections. So that I can get a sense of how you’re doing, please fill out this form once per lecture. (You will receive one point per lecture if you answer the form.)
Discussion: Please post all your course related questions on Canvas. If your question reveals your solution to a homework problem, please email me instead.
Assignments: You will receive one problem per class. I expect you to solve the problem with your group during the discussion (I’ll be there to answer questions). Once you have solved the problem, you should write up your solution on your own. In addition, there will be a project on a lecture topic of your choice.
| Assignment | Work Due | Self-grade Due |
|---|---|---|
| Problem Set 1 | Friday 1/12 | Monday 1/15 |
| Problem Set 2 | Friday 1/19 | Monday 1/22 |
| Problem Set 3 | Friday 1/26 | Monday 1/29 |
| Problem Set 4 | Friday 2/2 | Monday 2/5 |
| Project Proposal | Monday 1/22 | |
| Project | Friday 2/2 |
Resources: This class uses material from Chris Musco’s phenomenal graduate Algorithmic Machine Learning and Data Science course at NYU Tandon. For each class, I will post my typed notes and the handwritten slides we use in class.
| Class | Topic | Notes | Slides |
|---|---|---|---|
| Thursday 1/4 | Set Size Estimation | Notes | Slides |
| Monday 1/8 | Frequent Items | Notes | Slides |
| Tuesday 1/9 | Distinct Elements | Notes | Slides |
| Wednesday 1/10 | Load Balancing | Notes | Slides |
| Thursday 1/11 | Concentration Inequalities | Notes | Slides |
| Tuesday 1/16 | High-Dimensional Geometry | Notes | Slides |
| Wednesday 1/17 | Dimensionality Reduction | Notes | Slides |
| Thursday 1/18 | Similarity Estimation | Notes | Slides |
| Monday 1/22 | Singular Value Decomposition | Notes | Slides |
| Tuesday 1/23 | Power Method | Notes | Slides |
| Wednesday 1/24 | Spectral Graph Theory | Notes | Slides |
| Thursday 1/25 | Sketched Regression | Notes | Slides |
| Monday 1/29 | Fast JL Transform | Notes | Slides |
| Tuesday 1/30 | Sparse Recovery | Notes | Slides |