COS 521

Advanced Algorithm Design

Princeton University

 

Instructor: Matt Weinberg

 

TA: Divyarthi Mohan

 

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

 

Piazza: https://piazza.com/class/j7dw724yuexg7

 

Announcements will be posted below:

Project Guidelines: initial proposal due 11/30 (optional).

 

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. To submit your homework, email it to Divya at dm23 (at) cs (dot) Princeton (dot) edu by the deadline with subject line "COS 521 HW X."

 

Homework 1: due Monday 10/9 at 11:59pm.

Homework 2: due Thursday 11/9 at 11:59pm.

Homework 3: due Monday 11/27 at 11:59pm.

Homework 4: due Monday 12/18 at 11:59pm.

 

Lecture Notes: We will use lecture notes from previous iterations, and mostly follow the same schedule. You can get a headstart on the lecture notes here (along with optional deeper reading material), and notes will be posted below as the schedule becomes finalized.

 

Date

Topic

Reading Material

9/14

Hashing

Lecture Notes 1

9/19

Randomized Min-Cut

Lecture Notes 2

9/21

Concentration Bounds

Lecture Notes 3

9/26

Hashing to Reals

Lecture Notes 4

9/28

Linear Programs

Lecture Notes 5

10/3

LP Rounding

Lecture Notes 6 (slightly different from last year)

10/5

LP Duality

Lecture Notes 7 (different from last year)

10/10

Decisions under Uncertainty

Lecture Notes 8

10/12

Learning from Experts

Lecture Notes 9

10/17

Dimensionality Reduction

Lecture Notes 10

10/19

Markov Chains

Lecture Notes 11

10/24

Low-Rank Approximations

Lecture Notes 12

10/26

SVD and Stochastic Block Model

Lecture Notes 13

10/31

Fall Break

 

11/2

Fall Break

11/7

Semidefinite Progamming

Lecture Notes 14

11/9

Ellipsoid Algorithm

Lecture Notes 15 (slightly different from last year)

11/14

Submodular Minimization

Lecture Notes 16

11/16

Game Theory: Equilibria

Lecture Notes 17 (slightly different from last year)

11/21

Combinatorial Auctions I

Lecture Notes 18

11/23

Thanksgiving

11/28

Combinatorial Auctions II

Lecture Notes 19

11/30

Communication Complexity

Lecture Notes 20

12/5

Gradient Descent (Guest Lecture: Sanjeev Arora)

Lecture Notes 21

12/7

Differential Privacy (Guest Lecture: Mark Bun)

Lecture Notes 22

12/12

Coding Theory

12/14

Online Algorithms