Lec.
 Date
 Day
 Topic
 Notes

1 
Sep 12 
M 
Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Random Walks. 
First Day of Class

2 
Sep 14 
W 
Resistance, Energy and Rayleigh's Monotonicity Law, and Commute Time 

3 
Sep 16 
F 
Random Walks, Mixing Rates, and Eigenvectors 
Hwk 1 out [PDF]

4 
Sep 19 
M 
Random Walks, Mixing Rates, and Coupling 

5 
Sep 21 
W 
Mixing and Bounding Lambda_2 for Laplacians using path embedding. 

6 
Sep 23 
F 
Diffusion, SpringMass Systems, Laplacians, and Matrix Exponentials 

7 
Sep 26 
M 
Solving Linear Systems and Nested Dissection 

8 
Sep 28 
W 
More Nested Dissection, Minimum Degree Heuristic, and Fractals 

9 
Sep 30 
F 
Eigenvalues of directed graphs and the PerronFrobenius Theorem 
Hwk 1 due (Solutions PDF)

10 
Oct 03 
M 
Graph Cuts and Eigenvalues: Cheeger inequality 
Hwk 2 out [PDF]

11 
Oct 05 
W 
The Cheeger inequality Continued 

12 
Oct 07 
F 
Guest Lecture by Nick Harvey: Gragh Maximum Cut 

13 
Oct 10 
M 
Solving Linear Systems: The Basic Iterative Method,
Extrapolated Method, Chebyshev acceleration 

14 
Oct 12 
W 
Conjugate Gradient Method and Steepest Descent 

15 
Oct 14 
F 
Conjugate Gradient Method and Steepest Descent Continued


16 
Oct 17 
M 
Preconditioned Conjugate Gradient Method
and Low Stretch Spanning Trees 
Hwk 2 due (Solutions PDF) Hwk 3 out [PDF]

17 
Oct 19 
W 
AhlswedeWinter Thm, Graph Sparsification and Effective resistance 


Oct 21 
F 
MidSemester Break


Oct 24 
M 
FOCS Conference

18 
Oct 26 
W 
Proof of AhlswedeWinter Thm 

19 
Oct 28 
F 
O(m log n) Lapacian Solver 

20 
Oct 31 
M 
O(m log n) Lapacian Solver: Continued 
Hwk 3 due (Solutions PDF)

21 
Nov 02 
W 
Fiedler's Thm and Generalized Laplacian's 

22 
Nov 04 
F 
Spectral Methods for Planar Separators 
Hwk 4 out [PDF]

23 
Nov 07 
M 
Eigenvalues and Vectors by Iterative Methods 

24 
Nov 09 
W 
Fiedler's Thm Continued and Planar Embeddings 

25 
Nov 11 
F 
Arnoldi Iteration and Lanczos Algorithm 

26 
Nov 14 
M 
Arnoldi Iteration and Lanczos Algorithm and Symmetric Diagonally Dominate Systems 

27 
Nov 16 
W 
Eigenvalues and Vectors for Symmetric Tridiagonal Systems 

28 
Nov 18 
F 
Counting and Generating Random Spanning Trees 

29 
Nov 21 
M 
Generating Random Spanning Trees 
Hwk 4 due (Solutions PDF)


Nov 23 
W 
Thanksgiving Holiday


Nov 25 
F 
Thanksgiving Holiday

30 
Nov 28 
M 
Faster Random Walks and Generating Random Spanning Trees 

31 
Nov 30 
W 
Spectral Rounding [
]


32 
Dec 02 
F 
Random Walks with Restarts 

33 
Dec 05 
M 
Maximum Flow via Electrical Flow 

34 
Dec 07 
W 
Shortest Paths via Interior Point Methods 

35 
Dec 09 
F 
Homework Review [
]

Last Day of Class
