Schedule

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

Day Date Instr Topics Covered Notes and Readings Assignments
Mon Feb 01 Gary Lecture 1: Introduction and Course topics. [ClassNotes-Intro] pdf -note
-Recording
Wed Feb 03 Gary Lecture 2: Introduced Graph Laplacian, Effective Resistance, and Rayleigh's Monotonicity Law. [ClassNotes] pdf -note
-- Doyle and Snell: Random Walks and Electric Networks
[ScribeNotes] pdf
Recording
Fri Feb 05 Gary Lecture 3: Random Walks on Graphs and Cummute Time [ClassNotes] pdf -note
[ScribeNotes] pdf
Recording
Mon Feb 08 Gary Lecture 4: Random Walks on Graphs and Mixing [ClassNotes] pdf -note
-Recording
Wed Feb 10 Gary Lecture 5: Perron Frobenius and Symmetric Perron Frobenius. [ClassNotes] pdf -note
- Spielman-3
-Recording
Fri Feb 12 Break Day - No Class
Mon Feb 15 Gary Lecture 6: Differential Equations, Matrix Exponentials and Laplacians [ClassNotes] pdf -note
- Strang 5.4
-Recording
Wed Feb 17 Gary Lecture 7: Bounding Eigenvalues, Courant-Fischer, and Path Embedding. [ClassNotes] pdf -note
- Spielman-4 [ScribeNotes] pdf
-Recording
Fri Feb 19 HW Presentation Day
Mon Feb 22 Gary Lecture 8: Graph Sparsifiers and Ahlswede-Winter Thm [ClassNotes] pdf -note
- Spielman/Strivastava - Using AW [ScribeNotes] pdf
-Recording
Wed Feb 24 Court Hearing Day - No Class
Fri Feb 26 Gary Lecture 9: Matrix Chernoff Bounds, Ahlswede-Winter, Tropp [ClassNotes] pdf -note
- Using AW
-Recording
Mon Mar 01 Gary Lecture 10: Golden-Thompson using Weyl’s Majorant Theorem [ClassNotes] pdf -note
- VershyninNotes
-Recording
Wed Mar 03 Gary Lecture 11: Graph Cuts and Eigenvalues: Cheeger inequality [ClassNotes] pdf -note
- Guattery's Notes
-Recording
Fri Mar 05 Gary Lecture 12: Direct Linear Solvers and Nested Dissection for Planar Graphs" [ClassNotes] pdf -note
-[ScribeNotes] pdf
- [CLRS Chap 28]
-Recording
Mon Mar 08 Gary Lecture 13: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration [ClassNotes] pdf -note
- Hageman and Young 3-4 - Saad 4-7
-Recording
Wed Mar 10 Gary Lecture 14: Conjugate Gradient Method and Steepest Descent [ClassNotes] pdf -note
- Trefethen and Bau Chapter 38 - Saad Chap 5 - Painless CG
-Recording
Fri Mar 12 Junxing Lecture 15: On Computing the Min-Degree Elimination Ordering - Powerpoint Lecture
Mon Mar 15 Gary Lecture 16: Conjugate Gradient Method Analysis -Recording
Wed Mar 17 Gary Lecture 17: Fiedler's Thm and Generalized Laplacian's [ClassNotes] pdf -note
- Spielman Lecture 7 - Godsil Royle Chap 13 -Recording
Fri Mar 19 Mid-Semester Break - No Class
Mon Mar 22 HW Presentation Day
Wed Mar 24 Gary Lecture 18: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees [ClassNotes] pdf -note
- Lecture 19 Spielman
-Recording
Fri Mar 26 Gary Lecture 19: Eigenvalues and Vectors by Iterative Methods [ClassNotes] pdf -note
- Inverse Powering, see page 19 - Trefethen and Bau Chapter 27
-Recording
Mon Mar 29 Gary Lecture 20: Graph Maximum Cut via Spectral [ClassNotes] pdf -note
- Williamson Lecture 8 - Williamson Lecture 9
-Recording
Wed Mar 31 Gary Lecture 21: Graph Maximum Cut via Spectral [ClassNotes] pdf -note
- Williamson Lecture 8 - Williamson Lecture 9
-Recording
Fri Apr 02 Gary Lecture 22: Solving Graph Laplacians in Nearly O(m log n) time [ClassNotes] pdf -note
- CACM
-No Recording
Mon Apr 05 Break Day - No Class
Wed Apr 07 Gary Lecture 23: Solving Symmetric Diagonally Dominate Linear Systems [ClassNotes] pdf -note
-Recording
Fri Apr 09 HW Presentation Day
Mon Apr 12 Gary Lecture 24: Random Walks with Restarts and Spilling Paint [ClassNotes] pdf -note
Berkhin Painting - Andersen and Chung - Spielman's Notes
-Recording
Wed Apr 14 Gary Lecture 25: Counting Random Trees [ClassNotes-Counting] pdf -note
[ClassNotes-Generating] pdf -note
- Even Trees Chapter 2
-Recording
Fri Apr 16 Spring Carnival - No Class
Mon Apr 19 Gary Lecture 26: The Markov Chain Tree Theorem [ClassNotes] pdf -note
-Recording
Wed Apr 21 Gary Lecture 27: Generating Random Trees [ClassNotes-Generating] pdf -note
- Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees
Fri Apr 23 Gary Lecture 28: Random Walks and Matching [ClassNotes] pdf -note
- Spielman Notes on Matching
-Recording
Mon Apr 26 Gary Lecture 29: Maximum Flow via Electrical Flow [ClassNotes] pdf -note
- Lee Rao Srivastava
-Recording
Wed Apr 28 Gary Lecture 30: Nesterov and LRS MaxFlow [ClassNotes] pdf -note
- Lee Rao Srivastava
-Recording
Fri Apr 30 Study Day - No Class
Mon May 03 Gary Lecture 31: Probablity 101, The Exponential Dist., Low Diameter Decomposition [Classnotes] pdf -note
- LectureNotes
-Recording
Wed May 05 Gary Lecture 32: Exp. Dist. and Spanners [Classnotes] pdf -note -- LectureNotes
-- Shen Chen's Talk
-Recording
Fri May 07 HW Presentation Day