| Day | Date | Instr | Topics Covered | Notes and Readings | Assignments |
|---|---|---|---|---|---|
| Mon | Jan 13 | Gary | Lecture 1: Introduction and Course topics. | [ClassNotes-Intro]
pdf
-note |
|
| Wed | Jan 15 | Gary | Lecture 2: Introduced Graph Laplacian, Effective Resistance, and Energy. | [ClassNotes]
pdf
-note -- Doyle and Snell: Random Walks and Electric Networks [ScribeNotes] pdf |
|
| Fri | Jan 17 | Gary | Lecture 3: Energy and Rayleigh's Monotonicity Law | [ClassNotes]
pdf
-note [ScribeNotes] pdf |
|
| Mon | Jan 20 | Dr. Martin Luther King, Jr - No Class | |||
| Wed | Jan 22 | Gary | Lecture 4: Random Walks on Graphs and Cummute Time | [ClassNotes]
pdf
-note [ScribeNotes] pdf |
|
| Fri | Jan 24 | Gary | Lecture 5: Random Walks on Graphs and Mixing | [ClassNotes]
pdf
-note |
|
| Mon | Jan 27 | Gary | Lecture 6: Perron Frobenius and Symmetric Perron Frobenius. | [ClassNotes]
pdf
-note - Spielman-3 |
|
| Wed | Jan 29 | Gary | Lecture 7: Differtial Equations, Matrix Exponentials and Laplacians | [ClassNotes]
pdf
-note - Strang 5.4 |
|
| Fri | Jan 31 | Review Day | |||
| Mon | Feb 03 | Gary | Lecture 8: Graph Sparsifiers and Ahlswede-Winter Thm | [ClassNotes]
pdf
-note - Spielman/Strivastava - Using AW [ScribeNotes] pdf |
|
| Wed | Feb 05 | Gary | Lecture 9: Bounding Eigenvalues, Courant-Fischer, and Path Embedding. | [ClassNotes]
pdf
-note - Spielman-4 [ScribeNotes] pdf |
|
| Fri | Feb 07 | Gary | Lecture 10: Golden-Thompson using Weyl’s Majorant Theorem | [ClassNotes]
pdf
-note - VershyninNotes |
|
| Mon | Feb 10 | Gary | Lecture 11: Matrix Chernoff Bounds, Ahlswede-Winter, Tropp | [ClassNotes]
pdf
-note - Using AW |
|
| Wed | Feb 12 | Gary | Lecture 12: Graph Cuts and Eigenvalues: Cheeger inequality | [ClassNotes]
pdf
-note - Guattery's Notes |
|
| Fri | Feb 14 | Review Day | |||
| Mon | Feb 17 | Gary | Lecture 13: Direct Linear Solvers and Nested Dissection for Planar Graphs" | [ClassNotes]
pdf
-note -[ScribeNotes] pdf - [CLRS Chap 28] |
|
| Wed | Feb 19 | Gary | Lecture 14: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration | [ClassNotes]
pdf
-note - Hageman and Young 3-4 - Saad 4-7 |
|
| Fri | Feb 21 | Gary | Lecture 15: Conjugate Gradient Method and Steepest Descent | [ClassNotes]
pdf
-note - Trefethen and Bau Chapter 38 - Saad Chap 5 - Painless CG |
|
| Mon | Feb 24 | Gary | Lecture 16: Conjugate Gradient Method Continued | ||
| Wed | Feb 26 | Gary | Lecture 17: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees | [ClassNotes]
pdf
-note - Lecture 19 Spielman |
|
| Fri | Feb 28 | Review Day | |||
| Mon | Mar 02 | SCS Open House - No Class | |||
| Wed | Mar 04 | Gary | Lecture 18: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees continued | ||
| Fri | Mar 06 | Midsemester Break - No Class | |||
| Mon | Mar 09 | Spring Break - No Class | |||
| Wed | Mar 11 | Spring Break - No Class | |||
| Fri | Mar 13 | Spring Break - No Class | |||
| Mon | Mar 16 | Viral Shutdown - No Class | |||
| Wed | Mar 18 | Gary | Lecture 19: Fiedler's Thm and Generalized Laplacian's | [ClassNotes]
pdf
-note - Spielman Lecture 7 - Godsil Royle Chap 13 [ClassRecoding] MP4 |
|
| Fri | Mar 20 | Gary | Lecture 20: Eigenvalues and Vectors by Iterative Methods | [ClassNotes]
pdf
-note - Inverse Powering, see page 19 - Trefethen and Bau Chapter 27 |
|
| Mon | Mar 23 | Gary | Lecture 21: Graph Maximum Cut via Spectral | [ClassNotes]
pdf
-note - Williamson Lecture 8 - Williamson Lecture 9 |
|
| Wed | Mar 25 | Gary | Lecture 22: Graph Maximum Cut via Spectral | [ClassNotes-Version2]
pdf
-note - Williamson Lecture 8 - Williamson Lecture 9 |
|
| Fri | Mar 27 | Review Day | |||
| Mon | Mar 30 | Gary | Lecture 23: Solving Graph Laplacians in Nearly O(m log n) time | [ClassNotes]
pdf
-note - CACM |
|
| Wed | Apr 01 | Gary | Lecture 24: Solving Graph Laplacians in Nearly O(m log n) time | [ClassNotes]
pdf
-note - CACM |
|
| Fri | Apr 03 | Gary | Lecture 25: Random Walks with Restarts and Spilling Paint | [ClassNotes]
pdf
-note Berkhin Painting - Andersen and Chung - Spielman's Notes |
|
| Mon | Apr 06 | No Class - No Class | |||
| Wed | Apr 08 | Gary | Lecture 26: Solving Symmetric Diagonally Dominate | [ClassNotes]
pdf
-note |
|
| Fri | Apr 10 | Gary | Lecture 27: Counting Random Trees | [ClassNotes-Counting]
pdf
-note [ClassNotes-Generating] pdf -note - Even Trees Chapter 2 |
|
| Mon | Apr 13 | Gary | Lecture 28: The Markov Chain Tree Theorem | [ClassNotes-Generating]
pdf
-note - Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees |
|
| Wed | Apr 15 | Gary | Lecture 29: Generating Random Trees | [ClassNotes-Generating]
pdf
-note - Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees |
|
| Fri | Apr 17 | Gary | Lecture 30: Random Walks and Matching | [ClassNotes]
pdf
-note - Spielman Notes on Matching |
|
| Mon | Apr 20 | Zico | Lecture 31: Graph Neural Networks (Basics of machine learning, backpropagation) | Lecture date 4/20 [ClassNotes] pdf |
|
| Wed | Apr 22 | Zico | Lecture 32: backpropagation | Lecture date 4/22 | |
| Fri | Apr 24 | Zico | Lecture 33: Graph neural network model | Lecture date 4/24 [ClassNotes] pdf |
|
| Mon | Apr 27 | Review Day | |||
| Wed | Apr 29 | Gary | Lecture 34: Maximum Flow via Electrical Flow | [ClassNotes]
pdf
-note - Lee Rao Srivastava |
|
| Fri | May 01 | Gary | Lecture 35: Nesterov and LRS MaxFlow | [ClassNotes]
pdf
-note - Lee Rao Srivastava |