Schedule

Please keep in mind that this is very preliminary and will change.

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