LEC # | TOPICS |
---|---|
1 | Introduction |
2 | The Condition Number |
3 | The Largest Singular Value of a Matrix |
4 | Gaussian Elimination without Pivoting |
5 | Smoothed Analysis of Gaussian Elimination without Pivoting |
6 |
Growth Factors of Partial and Complete Pivoting Speeding up GE of Graphs with Low Bandwidth or Small Separators |
7 | Spectral Partitioning Introduced |
8 | Spectral Partitioning of Planar Graphs |
9 |
Spectral Paritioning of Well-Shaped Meshes and Nearest Neighbor Graphs Turner's Theorem for Bandwidth of Semi-Random Graphs |
10 |
Smoothed Analysis and Monotone Adversaries for Bandwidth and Graph Bisection McSherry's Spectral Bisection Algorithm |
11 |
Introduction to Linear Programming von Neumann's Algorithm, Primal and Dual Simplex Methods Duality |
12 |
Strong Duality Theorem of Linear Programming Renegar's Condition Numbers |
13 | Analysis of von Neumann's Algorithm |
14 | Worst-Case Complexity of the Simplex Method |
15 | The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane |
16 | The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane (cont.) |
17 | The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints |
18 | The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints: Distance Bound |
19 | The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints: Angle Bound and Overview of Phase 1 |