| Times | Tue Thu 11:00am - 12:15pm | ||
|---|---|---|---|
| Location | McCullough 115 | ||
| Instructor | John Tomlin (jtomlin5 at stanford) | Office Hours | By appointment |
| Course Assistants | Bertrand Decoster decoster at stanford | Tue 10-11 AM Thu 10-11 AM 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.- Graph Theory, Random walks and spanning trees
- The random walk connection
- The eigenvalue connection: matrices and graphs
- Markov chains
- Pagerank
- Networks and flows
- Definitions
- Max flows and min cuts
- Minimum cost flow
- Multicommodity flow
- Dynamic network flow (*)
- Linear programming
- Problem formulation
- Duality
- The simplex method
- Unimodularity
- Reductions and applications
- Integer Programming
- IP and MIP
- Cutting Planes
- Branch and bound, branch and cut
- Complexity(*)
- P versus NP. NP-completeness
- The primal-dual method. Randomized rounding methods
- Semi-definite relaxations and maximum cut
- Traveling Salesman Problems (TSP) (*)
- Algorithms and games (time permitting)(*)
- The stable marriage problem and applications
- Algorithms for Nash and market equilibria
Starred sections indicate advanced topics
