Times Tue Thu 11:00am - 12:15pm
Location 60-120
Instructor Amin Saberi (saberi at stanford) Office Hours By appointment
Course Assistants Edward Schmerling schmrlng at stanford
Reza Zadeh rezab at stanford
Wed 1-3pm
Tues 3:45-5:45pm
iCME Huang building basement

Required Texts

Recommended Texts

Topics

This course is targeting doctorate students with strong foundations in mathematics who wish to become more familiar with the design and analysis of discrete algorithms. An undergraduate course in algorithms is not a prerequisite, only familiarity with basic notions in linear algebra and discrete mathematics.
  1. Random walks and random spanning trees
    • Cayley's formula. Counting spanning trees of an arbitrary graph
    • The random walk connection: commute times and effective resistance
    • The eigenvalue connection: mixing times, Cheeger's inequality
    • Markov chains, approximate counting and approximate sampling
  2. Linear programming and network flows
    • The simplex method, LP duality, the ellipsoid method
    • Total unimodularity. Minimum cost maximum flows
    • Reductions and applications
  3. Approximation Algorithms
    • P versus NP. NP-completeness
    • The primal-dual method. Randomized rounding methods
    • Semi-definite relaxations and maximum cut
    • Traveling Salesman Problems
  4. Algorithms and games (time permitting)
    • The stable marriage problem and applications
    • Algorithms for Nash and market equilibria
    • Combinatorial auctions
    Topics illustrated with EE, CS and Bioinformatics applications.

Course Requirements

The requirements for this course are four homeworks (one every two weeks approximately), an in-class midterm examination and a final exam.