Calendar · Lecture Notes
MIT OpenCourseWare
Browse materials
Behavior of Algorithms
Art: Johannes Kepler, Konjukce Saturnu a Jupiteru Originál, 1596 · Public domain
- Instructor
- Prof. Daniel Spielman
- Term
- Spring 2002
- Level
- Graduate
- What's inside
- 1 lecture note · 1 reading · 45 other files · 3 web pages
- Materials open
- MIT OCW
About this course
Source: MIT OpenCourseWare 18.409 Behavior of Algorithms, Spring 2002, Prof. Daniel Spielman — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.
Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.
Before you start
Prerequisites are not listed here. Check MIT's own syllabus for this course.
How this course was organized
What's here, and what isn't
- A lecture sequence of 19 items is confirmed. No assignments or exams were found for this course, so it stays as organized materials rather than a full course order.
Not included here
5 items from the source could not be safely included:
- MIT's page format for this item wasn't recognized clearly enough to place it safely. (5 items)
Materials by section
Grouped by section, as MIT organized them. Not sequenced or ordered.
Lecture Notes
17 files
- Lecture 2 · The Condition Number · Lecture notes (Courtesy of Steve Weis. Used with permission.) Download
- Lecture 3 · The Largest Singular Value of a Matrix · Lecture notes (Courtesy of Arvind Sankar. Used with permission.) Download
- Lecture 4 · Gaussian Elimination Without Pivoting · Lecture notes (Courtesy of Matthew Lepinski. Used with permission.) Download
- Lecture 5 · Smoothed Analysis of Gaussian Elimination Without Pivoting · Lecture notes (Courtesy of Nitin Thaper. Used with permission.) Download
- Lecture 6 · Growth Factors of Partial and Complete Pivoting Speeding up GE of Graphs with Low… · Lecture notes (Courtesy of Brian Sutton. Used with permission.) Download
- Lecture 7 · Spectral Partitioning Introduced · Lecture notes (Courtesy of Michael Korn. Used with permission.) Download
- Lecture 8 · Spectral Partitioning of Planar Graphs · Lecture notes (Courtesy of Jan Vondrák. Used with permission.) Download
- Lecture 9 · Spectral Parititioning of Well-Shaped Meshes and Nearest Neighbor Graphs Turner’s Theorem… Download
- Lecture 10 · Smoothed Analysis and Monotone Adversaries for Bandwidth and Graph Bisection McSherry’s… Download
- Lecture 11 · Introduction to Linear Programming von Neumann’s Algorithm, Primal and Dual Simplex… · Lecture notes (Courtesy of José Correa. Used with permission.) Download
- Lecture 12 · Strong Duality Theorem of Linear Programming Renegar’s Condition Numbers · Lecture notes (Courtesy of Arvind Sankar. Used with permission.) Download
- Lecture 13 · Analysis of von Neumann’s Algorithm · Lecture notes (Courtesy of Nitin Thaper. Used with permission.) Download
- Lecture 14 · Worst-Case Complexity of the Simplex Method · Lecture notes (Courtesy of Brian Sutton. Used with permission.) Download
- Lecture 15 · The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane Download
- Lecture 16 · The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane… · Lecture notes (Courtesy of Mikhail Alekhnovitch. Used with permission.) Download
- Lecture 17 · The Expected Number of Facets of the Shadow of a Polytope Given by Gaussian Random… · Lecture notes (Courtesy of Steve Weis. Used with permission.) Download
- Lecture 19 · The Expected Number of Facets of the Shadow of a Polytope Given by Gaussian Random… · Lecture notes (Courtesy of Matthew Lepinski. Used with permission.) Download
Tools
25 files
- Code file in support of Lecture 1. This code was presented by the professor in order to facilitate… (EppBAP.mat) Download
- Code file in support of Lecture 2. This code was presented by the professor in order to facilitate… (airfoil1.mat) Download
- Code file in support of Lecture 3. This code was presented by the professor in order to facilitate… (airfoil2.mat) Download
- Code file in support of Lecture 4. This code was presented by the professor in order to facilitate… (art.m) Download
- Code file in support of Lecture 5. This code was presented by the professor in order to facilitate… (art3.m) Download
- Code file in support of Lecture 6. This code was presented by the professor in order to facilitate… (chew_circle.mat) Download
- Code file in support of Lecture 6. This code was presented by the professor in order to facilitate… (convert.m) Download
- Code file in support of Lecture 7. This code was presented by the professor in order to facilitate… (crossedGrid.m) Download
- Code file in support of Lecture 8. This code was presented by the professor in order to facilitate… (dat.mat) Download
- Code file in support of Lecture 9. This code was presented by the professor in order to facilitate… (epp.mat) Download
- Code file in support of Lecture 9. This code was presented by the professor in order to facilitate… (eppstein.mat) Download
- Code file in support of Lecture 10. This code was presented by the professor in order to facilitate… (fastfiedler.m) Download
- Code file in support of Lecture 10. This code was presented by the professor in order to facilitate… (gauss.m) Download
- Code file in support of Lecture 11. This code was presented by the professor in order to facilitate… (graph2A.m) Download
- Code file in support of Lecture 11. This code was presented by the professor in order to facilitate… (kahan.m) Download
- Code file in support of Lecture 11. This code was presented by the professor in order to facilitate… (kahan2.m) Download
- Code file in support of Lecture 12. This code was presented by the professor in order to facilitate… (laplacian.m) Download
- Code file in support of Lecture 12. This code was presented by the professor in order to facilitate… (mcrack.mat) Download
- Lecture 13 · Analysis of von Neumann’s Algorithm Download
- Code file in support of Lecture 14. This code was presented by the professor in order to facilitate… (noPivot.m) Download
- Code file in support of Lecture 15. This code was presented by the professor in order to facilitate… (ppConj.m) Download
- Code file in support of Lecture 16. This code was presented by the professor in order to facilitate… (ppDat.mat) Download
- Code file in support of Lecture 17. This code was presented by the professor in order to facilitate… (spectShow.m) Download
- Code file in support of Lecture 18. This code was presented by the professor in order to facilitate… (spectShow1.m) Download
- Code file in support of Lecture 19. This code was presented by the professor in order to facilitate… (v4.mat) Download
Readings
- Lecture 2 · The Condition Number Download
- Lecture 11 · Introduction to Linear Programming von Neumann’s Algorithm, Primal and Dual Simplex… · Readings (Courtesy of Marina Epelman and other students from Behavior of Algorithms. Used with permission.) Download
Other materials from this course
Course outline
Calendar · Lecture Notes
Lecture 2: The Condition Number
Calendar · Lecture Notes
Lecture 3: The Largest Singular Value of a Matrix
Calendar · Lecture Notes
Lecture 4: Gaussian Elimination without Pivoting
Calendar · Lecture Notes
Lecture 5: Smoothed Analysis of Gaussian Elimination without Pivoting
Calendar · Lecture Notes
Lecture 6: Growth Factors of Partial and Complete Pivoting Speeding up GE of Graphs with Low Bandwidth or Small Separators
Calendar · Lecture Notes
Lecture 7: Spectral Partitioning Introduced
Calendar · Lecture Notes
Lecture 8: Spectral Partitioning of Planar Graphs
Calendar · Lecture Notes
Lecture 9: Spectral Paritioning of Well-Shaped Meshes and Nearest Neighbor Graphs Turner’s Theorem for Bandwidth of Semi-Random Graphs
Calendar · Lecture Notes
Lecture 10: Smoothed Analysis and Monotone Adversaries for Bandwidth and Graph Bisection McSherry’s Spectral Bisection Algorithm
Calendar · Lecture Notes
Lecture 11: Introduction to Linear Programming von Neumann’s Algorithm, Primal and Dual Simplex Methods Duality
Calendar · Lecture Notes
Lecture 12: Strong Duality Theorem of Linear Programming Renegar’s Condition Numbers
Calendar · Lecture Notes
Lecture 13: Analysis of von Neumann’s Algorithm
Calendar · Lecture Notes
Lecture 14: Worst-Case Complexity of the Simplex Method
Calendar · Lecture Notes
Lecture 15: The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane
Calendar · Lecture Notes
Lecture 16: The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane (cont.)
Calendar · Lecture Notes
Lecture 17: The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints
Calendar · Lecture Notes
Lecture 18: The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints: Distance Bound
Calendar · Lecture Notes
Lecture 19: The Expected Number of Facets of the Shadow of a Polytope given by Gaussian Random Constraints: Angle Bound and Overview of Phase 1
MIT OpenCourseWare, Prof. Daniel Spielman, 18.409 Behavior of Algorithms, Spring 2002.
License: CC BY-NC-SA 4.0 · Edition: Spring 2002 · Open the original course on OCW ↗
Organized by RedLectern, independent of MIT and not endorsed by MIT.
Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.