| Day | Date | Instr | Topics Covered | Notes and Readings | Assignments |
|---|---|---|---|---|---|
| Wed | Sep 05 | Gary | Lecture 1: Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Energy. | [ClassNotes-Intro]
pdf
-note [ClassNotes] pdf -note -- Doyle and Snell: Random Walks and Electric Networks [ScribeNotes] pdf |
|
| Fri | Sep 07 | Gary | Lecture 2: Energy and Rayleigh's Monotonicity Law, and Random Walks on Graphs | [ClassNotes]
pdf
-note [ScribeNotes] pdf |
|
| Mon | Sep 10 | Gary | Lecture 3: Random Walks on Graphs and Mixing | [ClassNotes]
pdf
-note |
|
| Wed | Sep 12 | Gary | Lecture 4: Perron Frobenius and Symmetric Perron Frobenius. | [ClassNotes]
pdf
-note - Spielman-3 |
|
| Fri | Sep 14 | Gary | Lecture 5: Mixing Rates for Random Walks continued | [ClassNotes]
pdf
-note - Strang 5.4 |
|
| Mon | Sep 17 | Gary | Lecture 6: Bounding Eigenvalues, Courant-Fischer, and Path Embedding. | [ClassNotes]
pdf
-note - Spielman-4 |
|
| Wed | Sep 19 | Gary | Lecture 7: Laplacians, Differential Equations, and Matrix Exponentials | [ClassNotes]
pdf
-note - Strang 5.4 |
|
| Fri | Sep 21 | Gary | Lecture 8: Graph Sparsifiers and Ahlswede-Winter Thm | [ClassNotes]
pdf
-note - Spielman/Strivastava - Using AW |
|
| Mon | Sep 24 | Gary | Lecture 9: Matrix Chernoff Bounds, Ahlswede-Winter, Tropp | [ClassNotes]
pdf
-note - Using AW |
|
| Wed | Sep 26 | Gary | Lecture 10: Golden-Thompson using Weyl’s Majorant Theorem | [ClassNotes]
pdf
-note - VershyninNotes |
|
| Fri | Sep 28 | Gary | Lecture 11: Graph Cuts and Eigenvalues: Cheeger inequality | [ClassNotes]
pdf
-note - Guattery's Notes |
|
| Mon | Oct 01 | Gary | Lecture 12: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration | [ClassNotes]
pdf
-note - Hageman and Young 3-4 - Saad 4-7 |
|
| Wed | Oct 03 | Gary | Lecture 13: Conjugate Gradient Method and Steepest Descent | [ClassNotes]
pdf
-note - Trefethen and Bau Chapter 38 - Saad Chap 5 - Painless CG |
|
| Fri | Oct 05 | Gary | Lecture 14: Conjugate Gradient Method Continued | ||
| Mon | Oct 08 | Gary | Lecture 15: Direct Linear Solvers" | [ClassNotes]
pdf
-note - [CLRS Chap 28] |
|
| Wed | Oct 10 | Gary | Lecture 16: Nested Dissection for Planar Graphs | - [CLRS Chap 28] | |
| Fri | Oct 12 | Gary | Lecture 17: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees | [ClassNotes]
pdf
-note - Lecture 19 Spielman |
|
| Mon | Oct 15 | Gary | Lecture 18: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees continued | [ClassNotes]
pdf
-note - Lecture 19 Spielman |
|
| Wed | Oct 17 | Gary | Lecture 19: Fiedler's Thm and Generalized Laplacian's | [ClassNotes]
pdf
-note - Spielman Lecture 7 - Godsil Royle Chap 13 |
|
| Fri | Oct 19 | Midsemester Break - No Class | |||
| Mon | Oct 22 | Gary | Lecture 20: Eigenvalues and Vectors by Iterative Methods | [ClassNotes]
pdf
-note - Inverse Powering, see page 19 - Trefethen and Bau Chapter 27 |
|
| Wed | Oct 24 | Gary | Lecture 21: Continued: Eigenvalues and Vectors by Iterative Methods | - Inverse Powering, see page 19 - Trefethen and Bau Chapter 27 | |
| Fri | Oct 26 | Presidential Inauguration Day - No Class | |||
| Mon | Oct 29 | Gary | Lecture 22: Arnoldi Iteration and Lanczos Algorithm | [ClassNotes]
pdf
-note - Trefethen Bau Chap 33 - Trefethen Bau Chap 36 |
|
| Wed | Oct 31 | Gary | Lecture 23: Arnoldi Iteration and Lanczos Algorithm Cont | [ClassNotes]
pdf
-note - Trefethen Bau Chap 33 - Trefethen Bau Chap 36 |
|
| Fri | Nov 02 | Gary | Lecture 24: I: Graph Maximum Cut via Spectral | [ClassNotes]
pdf
-note - Williamson Lecture 8 - Williamson Lecture 9 |
|
| Mon | Nov 05 | Gary | Lecture 25: II: Graph Maximum Cut via Spectral | [ClassNotes]
pdf
-note - Williamson Lecture 8 - Williamson Lecture 9 |
|
| Wed | Nov 07 | Gary | Lecture 26: III: Graph Maximum Cut via Spectral | [ClassNotes]
pdf
-note - Williamson Lecture 8 - Williamson Lecture 9 |
|
| Fri | Nov 09 | Gary | Lecture 27: Solving Graph Laplacians in Nearly O(m log n) time | [ClassNotes]
pdf
-note - CACM |
|
| Mon | Nov 12 | Gary | Lecture 28: Homework Review Problem set 1 | ||
| Wed | Nov 14 | Gary | Lecture 29: Homework Review Problem set 2 | ||
| Fri | Nov 16 | Gary | Lecture 30: Solving Symmetric Diagonally Dominate | [ClassNotes]
pdf
-note |
|
| Mon | Nov 19 | Gary | Lecture 31: Random Walks and Matching | [ClassNotes]
pdf
-note - Spielman Notes on Matching |
|
| Wed | Nov 21 | Thanksgiving - No Class | |||
| Fri | Nov 23 | Thanksgiving - No Class | |||
| Mon | Nov 26 | Gary | Lecture 32: Counting Random Trees | [ClassNotes-Counting]
pdf
-note [ClassNotes-Generating] pdf -note - Even Trees Chapter 2 |
|
| Wed | Nov 28 | Gary | Lecture 33: The Markov Chain Tree Theorem | [ClassNotes-Generating]
pdf
-note - Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees |
|
| Fri | Nov 30 | Gary | Lecture 34: Generating Random Trees | [ClassNotes-Generating]
pdf
-note - Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees |
|
| Mon | Dec 03 | Gary | Lecture 35: Parallel Low Diameter Graph Decomposition using Delayed Start Times | [ClassNotes-Exponential Distribution ]
pdf
-note [ClassNotes-Low Diameter] pdf -note |
|
| Wed | Dec 05 | Gary | Lecture 36: Random Walks with Restarts and Spilling Paint | [ClassNotes]
pdf
-note Berkhin Painting - Andersen and Chung - Spielman's Notes |
|
| Fri | Dec 07 | Gary | Lecture 37: Random Walks with Restarts and Spilling Paint-continued |