| Date | Notes | Last Updated | Topics | Additional References |
|---|---|---|---|---|
| Week 1 | 2013 lecture 1 pdf 2013 lecture 2 pdf |
1/11/13 | Graphs, Trees, Random Walks and Markov Chains, Pagerank |
Random Walks Survey (Lovasz) Random Walks and Electric Networks (Doyle and Snell) Random Walks on Graphs (Aldous and Fill) |
| Weeks 2&3 | 2013 lecture3 pdf 2013 lecture4 pdf 2013 lecture5 pdf 2013 lecture6 pdf |
2/3/13 | Network Flow, Max-flow/Min-cut Algorithms and Applications Dynamic Programming |
CS 261 Max-flow Notes (Lec. 9-11) (Trevisan) Ford and Fulkerson Ch. 1 Kleinberg and Tardos Ch. 6,7 Beale, "Introduction to Optimization" Ch 12 |
| Week 4 | 2013 lecture 7 pdf There is no 2013 lecture 8 (In class midterm) |
2/5/13 | Review and Midterm | A New Approach to the Minimum Cut Problem (Karger and Stein) |
| Week 5 | 2013 lecture 9 pdf 2013 lecture 10 pdf |
2/5/13 | Matching and multicommodity flow. Linear Programming and Duality |
KT, Ch 1 Ford and Fulkerson, Ch 1 |
| Weeks 6&7 | 2013 lecture 11 pdf 2013 lecture 12 pdf 2013 lecture 13 pdf (There is no 2013 lecture 14) |
2/19/13 | Linear programming and the Simplex Method |
Dantzig, "LP and Extensions" Williams, "Model Building in Mathematical Programming" Chvatal, "Linear Programming" Schriver, "Theory of linear and integer programming" |
| Week 8 | 2013 lecture 15 pdf notes pdf zero-one stuff pdf special cases pdf 2013 lecture 16 pdf |
3/1/13 | Integer Programming | Nemhauser and Wolsey, "Integer and combinatorial optimization" |
| Week 9 | 2013 lecture 17 pdf 2013 lecture 18 pdf notes pdf |
3/6/13 | Branch and Bound, Enumeration Reduction, Problem Classes. |
The NP Compendium
Kleinberg and Tardos Ch. 8 |
| Week 10 | 2013 lecture 19 pdf 2013 lecture 20 pdf |
3/15/13 | Approximation Algorithms, Auctions and Review |
Kleinberg and Tardos Ch. 10-11 Edelman et al. Krishna, "Auction theory" |
Please send any error reports or requests to Bertrand Decoster (decoster [AT] stanford [DOT] edu).
