The Behavior of Algorithms
18.409 Topics in Theoretical Computer Science
Instructor:
Dan Spielman.
Tuesday/Thursday 2:30-4:00 in 3-270
Here are links to the course announcement,
useful matlab code, and lecture-specific
notes:
- Lecture 2 (2/12/02),
on the condition number. Lots of matlab code here.
- Lecture 3 (2/14/02),
on the largest singluar value of a matrix.
- Lecture 4 (2/21/02),
on Gaussian elimination without pivoting.
- Lecture 5 (2/26/02),
Smoothed analysis of Gaussian elimination without pivoting.
- Lecture 6 (2/28/02),
Growth factors of partial and complete pivoting.
Speeding up GE of graphs with low bandwidth or small separators.
- Lecture 7 (3/05/02),
Spectral Partitioning introduced
- Lecture 8 (3/07/02),
Spectral Partitioning of planar graphs.
- Lecture 9 (3/12/02),
Spectral paritioning of well-shaped meshes and nearest neighbor graphs.
Turner's theorem for bandwidth of semi-random graphs.
- Lecture 10 (3/14/02),
Smoothed analysis and monotone adversaries for bandwidth and graph
bisection. McSherry's spectral bisection algorithm.
- Lecture 11 (3/19/02),
Introduction to Linear Programming. von Neumann's algorithm,
primal and dual simplex methods, and duality.
- Lecture 12 (3/21/02),
Strong duality theorem of linear programming. Renegar's condition numbers.
- Lecture 13 (4/2/02),
Analysis of von Neumann's algorithm
- Lecture 14 (4/9/02),
Worst-case complexity of the simplex method.
- Class on 4/11/02 cancelled due to birth of guest lecturer's babys.
- No Class on 4/16/02 due to Patriot's Day.
- Lecture 15 (4/18/02),
On the expected number of facts of the convex hull of
Gaussian random points in the plane.
- Lecture 16 (4/23/02),
On the expected number of facets of the convex hull of
Gaussian random points in the plane, continued.
- Lecture 17 (4/25/02),
On the expected number of facets of the shadow of
a polytope given by Gaussian random constraints.
- Lecture 18 (4/30/02),
On the expected number of facets of the shadow of
a polytope given by Gaussian random constraints: distance bound.
- Lecture 19 (5/2/02),
On the expected number of facets of the shadow of
a polytope given by Gaussian random constraints: angle bound
and overview of phase 1.
- Class presentations, May 7: Arvind Sankar
- Class presentations, May 9: Brian Sutton, Matt Lepinski, Steve Weis
- Class presentations, May 14: Michael Korn, Jan Vondrak, Mikhail Alekhnovitch
- Class presentations, May 16: Jose Correa, Larry Guth