| Day | Date | Instr | Topics Covered | Notes and Readings | Assignments |
|---|---|---|---|---|---|
| Mon | Sep 09 | Gary | Lecture 1: Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Random Walks | ClassNotes - Doyle and Snell: Random Walks and Electric Networks | |
| Wed | Sep 11 | Gary | Lecture 2: Resistance, Energy and Rayleigh's Monotonicity Law, and Commute Time | ClassNotes | |
| Fri | Sep 13 | Gary | Lecture 3: Mixing Rates for Random Walks | ClassNotes - Lovasz Notes | |
| Mon | Sep 16 | Gary | Lecture 4: Bounding Eigenvalues and Symmetric Perron Frobenius for Laplacians using path embedding. | ClassNotes - Spielman-3 | |
| Wed | Sep 18 | Gary | Lecture 5: Bounding Eigenvalues, Courant-Fischer, and Path Embedding. | ClassNotes - Spielman-4 | |
| Fri | Sep 20 | Euiwoong | Lecture 6: No Lecture | ||
| Mon | Sep 23 | Gary | Lecture 7: Laplacians, Differential Equations, and Matrix Exponentials | ClassNotes- Strang 5.4 | |
| Wed | Sep 25 | Gary | Lecture 8: Graph Sparsifiers and Ahlswede-Winter Thm | ClassNotes- Spielman/Strivastava - Using AW | |
| Fri | Sep 27 | Richard | Lecture 9: Statistical Leverage Scores and Row Sampling | Slides- Arxiv paper | |
| Mon | Sep 30 | Gary | Lecture 10: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration | ClassNotes- Hageman and Young 3-4 - Saad 4-7 | |
| Wed | Oct 02 | Gary | Lecture 11: Conjugate Gradient Method and Steepest Descent | ClassNotes- Trefethen and Bau Chapter 38 - Saad Chap 5 - Painless CG | |
| Fri | Oct 04 | Gary | Lecture 12: Conjugate Gradient Method Continued | - | |
| Mon | Oct 07 | Gary | Lecture 13: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees | ClassNotes- Lecture 19 Spielman | |
| Wed | Oct 09 | Euiwoong | Lecture 14: Homework Review | - | |
| Fri | Oct 11 | Rest Break - No Class | |||
| Mon | Oct 14 | Gary | Lecture 15: Direct Linear Solvers" | ClassNotes- [CLRS Chap 28] | |
| Wed | Oct 16 | Gary | Lecture 16: Graph Cuts and Eigenvalues: Cheeger inequality | ClassNotes- Guattery's Notes | |
| Fri | Oct 18 | Midsemester Break - No Class | |||
| Mon | Oct 21 | Gary | Lecture 17: Eigenvalues and Vectors by Iterative Methods | ClassNotes- Inverse Powering, see page 19 - Trefethen and Bau Chapter 27 | |
| Wed | Oct 23 | Gary | Lecture 18: Fiedler's Thm and Generalized Laplacian's | ClassNotes- Spielman Lecture 7 - Godsil Royle Chap 13 | |
| Fri | Oct 25 | Gary | Lecture 19: Arnoldi Iteration and Lanczos Algorithm | ClassNotes- Trefethen Bau Chap 33 - Trefethen Bau Chap 36 | |
| Mon | Oct 28 | FOCS Conference - No Class | |||
| Wed | Oct 30 | Gary | Lecture 20: Solving Graph Laplacians in Nearly O(m log n) time | ClassNotes- CACM | |
| Fri | Nov 01 | Gary | Lecture 21: Graph Laplacians Solver Cont., Symmetric Diagonally Dominate | ClassNotes | |
| Mon | Nov 04 | Gary | Lecture 22: Symmetric Diagonally Dominate Solvers; Maximum Flow | ClassNotes SDD- ClassNotes MaxFlow - Lee Rao Srivastava | |
| Wed | Nov 06 | Gary | Lecture 23: Maximum Flow via Electrical Flow Cont. | ClassNotes | |
| Fri | Nov 08 | Gary | Lecture 24: Nesterov and MaxFlow | ClassNotes | |
| Mon | Nov 11 | Gary | Lecture 25: Computing Minimum Energy Flow | ClassNotes- KOSZ Min Flow | |
| Wed | Nov 13 | Gary | Lecture 26: Random Walks and Matching | ClassNotes- Spielman Notes on Matching | |
| Fri | Nov 15 | Gary | Lecture 27: Counting and Generating Random Trees | ClassNotes Counting- ClassNotes Generating - Even Trees Chapter 2 - Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees | |
| Mon | Nov 18 | Gary | Lecture 28: Faster Random Walks and Generating Random Spanning Trees | ClassNotes- Wilson: Generating Random Spanning Trees - Propp and Wilson: Generating Random Spanning Trees - Madry's Thesis, see Chap 7 | |
| Wed | Nov 20 | Jacub | Lecture 29: Bartal Trees and Low Stretch Spanning Trees | Slides - Paper | |
| Fri | Nov 22 | Shen Chen | Lecture 30: Parallel Low Diameter Graph Decomposition using Delayed Start Times | - | |
| Mon | Nov 25 | Gary | Lecture 31: Random Walks with Restarts | Spielman's Notes | |
| Wed | Nov 27 | Thanksgiving - No Class | |||
| Fri | Nov 29 | Thanksgiving - No Class | |||
| Mon | Dec 02 | Gary | Lecture 32: Random Walks with Restarts and Spilling Paint | Berkhin Painting - | |
| Wed | Dec 04 | Gary | Lecture 33: Random Walks with Restarts and Spilling Paint-continued | Andersen and Chung - ClassNotes | |
| Fri | Dec 06 | Gary | Lecture 34: Homework Review |