Day  Date  Instr  Topics Covered  Notes and Readings  Assignments 

Mon  Jan 13  Gary  Lecture 1: Introduction and Course topics.  [ClassNotesIntro]
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  Spielman3 

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 AhlswedeWinter Thm  [ClassNotes]
pdf
note  Spielman/Strivastava  Using AW [ScribeNotes] pdf 

Wed  Feb 05  Gary  Lecture 9: Bounding Eigenvalues, CourantFischer, and Path Embedding.  [ClassNotes]
pdf
note  Spielman4 [ScribeNotes] pdf 

Fri  Feb 07  Gary  Lecture 10: GoldenThompson using Weylâ€™s Majorant Theorem  [ClassNotes]
pdf
note  VershyninNotes 

Mon  Feb 10  Gary  Lecture 11: Matrix Chernoff Bounds, AhlswedeWinter, 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 34  Saad 47 

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  [ClassNotesVersion2]
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  [ClassNotesCounting]
pdf
note [ClassNotesGenerating] pdf note  Even Trees Chapter 2 

Mon  Apr 13  Gary  Lecture 28: The Markov Chain Tree Theorem  [ClassNotesGenerating]
pdf
note  Broder Generating Random Spanning Tree  Aldous Generating Random Spanning Trees 

Wed  Apr 15  Gary  Lecture 29: Generating Random Trees  [ClassNotesGenerating]
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 