Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design 

Moses Charikar
Chandra Chekuri

Spring 2004

 

General Information | Schedule and Readings | What's New?

Approximate Schedule

Week 1: Universal Hashing

Week 2: Linear Programming: Introduction, Simplex Algorithm

Week 3: LP: Farkas Lemma, Duality, Ellipsoid Algorithm 

Week 4: LP: Ellipsoid Algorithm, cone-LP, SDP

Week 5: 

Week 6: 

Week 7: 

Week 8: 

Week 9: 

Week 10: 

Week 11: 

Week 12: 

Homeworks

Homework 0: Send mail to moses AT cs DOT princeton DOT edu and chekuri "at" research "dot" bell-labs "dot" com with COS 521 in the subject header and the following information:

  1. Your name, year and department.

  2. Your math background and familiarity with topics relevant to the class.

  3. Any comments or suggestions for topics to be covered.

Basic Exercises (only for practice, do not turn in) (ps,pdf)

Homework 1 (due Tue, March 9) (ps,pdf)
(Feb 27) corrected statement of Problem 2

Homework 2 (due Thu, April 1) (ps,pdf)

Homework 3 (due Thu, April 15) (ps,pdf)

Homework 4 (due Mon, May 10) (ps,pdf)

Final (due Mon, May 17) (ps,pdf)

 

References

 

  1. Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan

  2. Michel Goemans' notes on Linear Programming
    (Read Sections 1-5 in preparation for lectures on LP).

  3. Read Sections 6-12 of LP notes for material covered in lectures 3-5

  4. For material covered in lectures 6-7, read scribe notes from Michel Goemans' Advanced Algorithms course:  Lecture 4, Lecture 5, and Lecture 6

  5. For initial material on cone-LP and SDP, read Farid Alizadeh's lecture notes: Lecture 1 and Lecture 2.

  6. Introductory material on network flows from MIT course on Advanced Algorithms (Fall 2003)
    (Read in preparation for lectures on network flows).

  7. Lecture notes for LP based approximation algorithm for minimum multicut and balanced cut.

  8. The new SDP based approximation algorithm for sparsest cut and balanced cut is available here.

  9. For lower bounds on randomized algorithms, see Sections 2.1 and 2.2 of the randomized algorithms text book.

  10. For notes on applications on expanders and connections between eigenvalues and expansion, look here (section 2) and here.

 

 Lecture Notes

 

2/03/04 (ps,pdf)   Shien Jin Ong

2/05/04 (ps,pdf)   Wolfgang Mulzer

2/26/04 (ps,pdf)   C. Seshadhri

 

 

Template for scribe notes. Sample LaTeX files (1.tex,2.tex,3.tex,4.tex,5.tex)

Last updated by Moses Charikar, 12-May-2004 05:09 AM