COS 521

Advanced Algorithm Design

Princeton University

 

Instructors: Mark Braverman, Matt Weinberg

 

TAs: Linda Cai, Zhou Lu

 

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/8773/discussion/. If you are enrolled in the course, you should have access to Ed. Please email the instructors if you cannot access Ed.

 

codePost: Course assignments will be submitted to codePost. You can enroll in the course using this link (must use an @princeton or @cs.princeton email address).

 

Announcements will be posted below:

-         Guidelines for the final exam/project are posted: final guidelines.

-         The final exam is now posted: final exam.

 

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. Submit your homework through codePost here.

 

Lecture Notes: We will use lecture notes from previous iterations, and mostly follow the same schedule. Below is a tentative schedule:

 

Date

Topic

Reading Material

9/2

Randomized Min-Cut

Lecture Notes 1

9/7

LP Rounding I

Lecture Notes 2

9/9

LP Rounding II

Lecture Notes 3

9/14

LP Duality

Lecture Notes 4

9/16

Semi-Definite Programs

Lecture Notes 5

9/21

Hashing

Lecture Notes 6

9/23

Concentration Inequalities

Lecture Notes 7

9/28

Martingales

See Ed

9/30

Random Walks and Markov Chains

Lecture Notes 9

10/5

Multiplicative Weights

Lecture Notes 10

10/7

Johnson-Lindenstrauss

Lecture Notes 11

10/12

Locality-Sensitive Hashing and Approximate Nearest Neighbors

Lecture Notes 12

10/14

Low-Rank Approximations and SVD

Lecture Notes 13

10/19

Fall Break

 

10/21

Fall Break

 

10/26

Coding Theory

Lecture Notes 14

10/28

Online Algorithms I

Lecture Notes 15

11/2

Online Algorithms II

Lecture Notes 16

11/4

Computation of Nash

Lecture Notes 17

11/9

Ellipsoid Algorithm

Lecture Notes 18

11/11

Submodular Minimization

Lecture Notes 19

11/16

Communication Complexity

Lecture Notes 20

11/18

Hashing to Reals

Lecture Notes 21

11/23

Differential Privacy

Lecture Notes 22

11/25

Thanksgiving Break

 

11/30

Combinatorial Auctions I

Lecture Notes 23

12/2

Combinatorial Auctions II

Lecture Notes 24