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?

Course Description

The course covers advanced methods of algorithmic design and analysis: data structures, linear programming, network flows, matchings, randomized algorithms and online algorithms. In addition, special topics will be covered based on student preferences.

Students will be expected to have a basic knowledge of algorithms, graph theory and probability.

Prerequisites: COS 226, COS 341, COS 423 (or equivalent). 


Problem sets will be handed out in class every two weeks. There will be a take home final exam. All students (credit as well as audit) will be expected to scribe lecture notes for some classes during the semester. 70% of the grade will be based on the homework average and 30% on the take home final. If you do a good job of scribing, we will drop your lowest homework score in computing the homework average.

Syllabus (tentative)

Week 1: Universal hashing

Week 2: Linear Programming (LP)

Week 3: LP contd.

Week 4: LP: ellipsoid method

Week 5: Network flows

Week 6: flows

Week 7: flows - integrality of polyhedra, totally unimodular matrices

Week 8: Matchings

Week 9: Matching in general graphs

Week 10: Topics in Randomized algorithms

Week 11: Randomized algorithms

Week 12: Special topic


Administrative Information

Lectures: Tu Thu 1:30-2:50 , Room: 102 CS building

(Occasionally, we will have additional lectures to make up for lost lectures. This will be announced in class.)

Instructors : 
Moses Charikar - 305 CS Building - 258-7477 
Office Hours: by appointment
Chandra Chekuri - 908-582-1204 chekuri "at" research "dot" bell-labs "dot" com

Graduate Coordinator: Melissa Lawson - 410 CS Building - 258-1746

Course Secretary: Mitra Kelly - 323 CS Building - 258-4562

Mailing List:

Teaching Assistants: none

Last updated by Moses Charikar, 07-Feb-2004 12:57 AM