Courses:

Behavior of Algorithms >> Content Detail



Calendar / Schedule



Calendar

LEC #TOPICS
1Introduction
2The Condition Number
3The Largest Singular Value of a Matrix
4Gaussian Elimination without Pivoting
5Smoothed Analysis of Gaussian Elimination without Pivoting
6Growth Factors of Partial and Complete Pivoting

Speeding up GE of Graphs with Low Bandwidth or Small Separators
7Spectral Partitioning Introduced
8Spectral Partitioning of Planar Graphs
9Spectral Paritioning of Well-Shaped Meshes and Nearest Neighbor Graphs

Turner's Theorem for Bandwidth of Semi-Random Graphs
10Smoothed Analysis and Monotone Adversaries for Bandwidth and Graph Bisection

McSherry's Spectral Bisection Algorithm
11Introduction to Linear Programming

von Neumann's Algorithm, Primal and Dual Simplex Methods

Duality
12Strong Duality Theorem of Linear Programming

Renegar's Condition Numbers
13Analysis of von Neumann's Algorithm
14Worst-Case Complexity of the Simplex Method
15The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane
16The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane (cont.)
17The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints
18The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints: Distance Bound
19The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints: Angle Bound and Overview of Phase 1

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.