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
• homework 4: due 11/9

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
8	9/29	Dimension Reduction and Johnson-Lindenstrauss Lemma
Linear Programming & Semidefinite Programming
9	10/1	LP Duality
10	10/6	LP Rounding
11	10/8	Simplex Algorithm
	10/13	Fall Break
	10/15	Fall Break
12	10/20	Ellipsoid Algorithm
13	10/22	Semidefinite Programming
14	10/27	Submodular Minimization
Other Algorithmic Topics
15	10/29	Online Algorithms
16	11/3	Parameterized Complexity
17	11/5	Coding Theory
18	11/10	Distance Oracles
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