Randomized Algorithms for Data Science
Instructor: R. Teal Witter. Please call me Teal.
Class Times: Tuesdays and Thursdays from 2:45 to 4:00pm in Kravis 164.
Office Hours: Mondays and Thursdays from 12:30 to 2pm in Adams 213.
Problem Sets: Your primary opportunity to learn the material will be on problem sets. You may work with others to solve the problems, but you must write your solutions by yourself, and explicitly acknowledge any outside help (e.g., websites, people, LLMs).
Quizzes: There will be short quizzes at the beginning of (randomly) selected classes. These quizzes will test your understanding of the problem sets and the concepts from the prior week.
Exams: The two midterm exams are the primary method of assessing your understanding of the material.
Project: The project offers a chance to explore an area that interests you, practice writing high quality code, and develop your ability to communicate technical ideas to an audience.
Resources: This class is based on Chris Musco’s phenomenal algorithmic machine learning and data science course at NYU. While we do not have a textbook, I have prepared written notes for every lecture; I highly recommend you read the notes before each class.
| Week | Tuesday | Thursday | Slides | Assignments |
| Streaming & Sketching | ||||
| Week 1 (1/20 and 1/22) | Math Review | Set Size Estimation | ||
| Week 2 (1/27 and 1/29) | Set Size Estimation | Frequent Items | ||
| Week 3 (2/3 and 2/5) | Frequent Items | Distinct Elements | ||
| Week 4 (2/10 and 2/12) | Distinct Elements | Load Balancing | ||
| Week 5 (2/17 and 2/19) | Load Balancing | Concentration Inequalities | ||
| Week 6 (2/24 and 2/26) | Concentration Inequalities | High-Dimensional Geometry | ||
| Week 7 (3/3 and 3/5) | High-Dimensional Geometry | Midterm Exam | ||
| Week 8 (3/10 and 3/12) | Dimensionality Reduction | Dimensionality Reduction | ||
| Week 9 (3/17 and 3/19) | Spring Break (No Class) | Spring Break (No Class) | ||
| Linear Algebra & Spectral Methods | ||||
| Week 10 (3/24 and 3/26) | Similarity Estimation | Similarity Estimation | ||
| Week 11 (3/31 and 4/2) | Singular Value Decomposition | Singular Value Decomposition | ||
| Week 12 (4/7 and 4/9) | Spectral Graph Theory | Spectral Graph Theory | ||
| Week 13 (4/14 and 4/16) | Sketched Regression | Sketched Regression | ||
| Week 14 (4/21 and 4/23) | Explainable AI | Explainable AI | ||
| Week 15 (4/28 and 4/30) | Explainable AI | Midterm Exam | ||
| Week 16 (5/5 and 5/7) | Project Preparation | Reading Day (No Class) | ||
| Week 17 (5/12 and 5/14) | Project Presentation 7-10pm | Finals (No Class) | ||