| 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
- Algorithm Design by Kleinberg and Tardos [KT]
Recommended Texts
- Discrete Mathematics by Lovasz, Pelikan and Vesztergombi [LPV] (available here for Stanford IPs)
- A Course in combinatorics by van Lint and Wilson [vLW]
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.- 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
- Linear programming and network flows
- The simplex method, LP duality, the ellipsoid method
- Total unimodularity. Minimum cost maximum flows
- Reductions and applications
- Approximation Algorithms
- P versus NP. NP-completeness
- The primal-dual method. Randomized rounding methods
- Semi-definite relaxations and maximum cut
- Traveling Salesman Problems
- Algorithms and games (time permitting)
- The stable marriage problem and applications
- Algorithms for Nash and market equilibria
- Combinatorial auctions
