Instructor	Huacheng Yu
Lectures	Monday/Wednesday 1:20-2:40pm
TAs	Rohit Agarwal, Frederick Qiu
Location	Friend Center 008
Office hours	Huacheng: M/W 2:45-3:45pm @ CS310 Rohit: T 1-2pm, Th 11am-noon @ CS 3rd floor common space Frederick: F 1:30-3:30pm @ CS 3rd floor common space

For contact information, course description, collaboration/grading policy, etc., please see the course infosheet.

Ed

We will use Ed for course discussion. The link is: https://edstem.org/us/courses/85871/discussion. If you are enrolled in the course, you should have access to Ed. Please email the instructor if you cannot access Ed.

Homework

Homeworks will be posted below when they become available. Here is a LaTeX template you may use for the homework, and here is a short guide to LaTeX. Feel free to visit office hours for help installing/setting up LaTeX. Please submit your solutions to Gradescope: https://www.gradescope.com/courses/1114749.

• homework 1: due 9/21
• homework 2: due 10/5
• homework 3: due 10/26 10/28
• homework 4: due 11/9 11/11

Lecture notes and schedule

For most lectures, we will use lecture notes from previous iterations. Below is a tentative schedule.

Lecture #	Date	Topic	Lecture notes
Randomized Algorithms
1	9/3	Randomized Min-Cut	Lecture 1
2	9/8	Concentration Inequalities	Lecture 2
3	9/10	Hashing I	Lecture 3
4	9/15	Hashing II	Lecture 4
5	9/17	Locality-Sensitive Hashing and Approximate Nearest Neighbors	Lecture 5
6	9/22	Streaming I	Lecture 6
7	9/24	Streaming II	Lecture 7
8	9/29	Dimension Reduction and Johnson-Lindenstrauss Lemma	Lecture 8
Linear Programming & Semidefinite Programming
9	10/1	LP Duality	Lecture 9
10	10/6	LP Rounding	Lecture 10
11	10/8	Simplex Algorithm	Lecture 11
	10/13	Fall Break
	10/15	Fall Break
12	10/20	Ellipsoid Algorithm	Lecture 12
13	10/22	Semidefinite Programming	Lecture 13
14	10/27	Submodular Minimization	Lecture 14
Other Algorithmic Topics
15	10/29	Online Algorithms	Lecture 15
16	11/3	Parameterized Complexity	Lecture 16
17	11/5	Coding Theory	Lecture 17
18	11/10	Distance Oracles	Lecture 18
19	11/12	Graph Spanners
20	11/17	Graph Sparsifiers
21	11/19	Low-Rank Approximations and SVD
22	11/24	External Memory Algorithms
	11/26	Thanksgiving
Project Presentations
23	12/1	Project Presentations
24	12/3	Project Presentations