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