Princeton University |
Computer Science 521
|
|
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.
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.
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 |
(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 moses_AT_cs.princeton.edu
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 mml_AT_cs.princeton.edu
Course Secretary: Mitra Kelly - 323 CS Building - 258-4562 mkelly_AT_cs.princeton.edu
Mailing List: https://lists.cs.princeton.edu/mailman/listinfo/cos521
Teaching Assistants: noneLast updated by Moses Charikar, 07-Feb-2004 12:57 AM