Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design

Bernard Chazelle

Fall 2001
Directory
General Information | Assignments | Lecture Slides

Course Summary

Advanced methods of algorithmic design and analysis: data structures, network flows, and linear programming (Karmarkar's and ellipsoid algorithms). Randomized algorithms. Lattice reduction. Techniques for approximation algorithms: primal-dual/ positive semidefinite programming. Dimension reduction techniques, number theoretic algorithms.

Week 1: Dynamic programming, linear selection, Dyer & Megiddo's algorithm for linear programming.

Week 2: LLL Lattice basis reduction and applications (Diophantine approximation, Mertens' conjecture, Knapsack cryptosystems, polynomial factoring).

Week 3: Review of finite fields and characters. Riemann's hypothesis for curves and varieties.

Week 4: Pseudo-randomness: low bias via characters.

Week 5: The soft heap

Week 6: Interactive proofs

Week 7: Expanders

Week 8: Semidefinite programming: Lovasz's theta function, Goemans-Williamson MAXCUT algorithm, MAXDICUT, etc

Week 9: Linear programming, duality, maxflow-mincut

Week 10: Ellipsoid algorithm

Administrative Information

Lectures: TTh 1:30-2:50, Room: COS 402

Professor: Bernard Chazelle - 404 CS Building - 258-5380 chazelle@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Teaching Assistants: TBA