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 |