MIT OpenCourseWare

Browse materialsMIT 6.854J · Fall 2008

Advanced Algorithms

Subject: Mathematics

Art: not stated, Fletcher's Combined Block Telegraph Apparatus and Bell, 1889 · Public domain

Instructor: Prof. Michel Goemans
Term: Fall 2008
Level: Graduate
What's inside: 12 problem sets · 6 solutions · 1 lecture note · 1 reading · 49 other files · 4 web pages
Materials open: MIT OCW

Other versions of this course

6.854J · Fall 2008 · Study here (this version)
6.854J · Fall 2005 · Study here

Start here

Start course: Lecture 1: Fibonacci heaps Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 6.854J Advanced Algorithms, Fall 2008, Prof. Michel Goemans — 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.

Has MIT solutions 6 files in this course are named by MIT as solutions.

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

MIT's own materials here did not support a verified, course-wide order, so they are grouped by section instead.

Not included here

7 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)
Referenced in a table, but without MIT's own verified order, so it isn't used to claim a sequence. (2 items)

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

20 files

Assignments

18 problem sets

1 image

Ellipses on an axisJPEG image Open ↗

Study Materials

26 files

Other materials from this course

MIT OpenCourseWare, Prof. Michel Goemans, 6.854J Advanced Algorithms, Fall 2008.

License: CC BY-NC-SA 4.0 · Edition: Fall 2008 · 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.

Advanced Algorithms

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Study Materials

Other materials from this course

Lecture 1: Fibonacci heaps

Lecture 2: Network flows

Lecture 3: Maximum flow; minimum cost circulation

Lecture 4: Goldberg-Tarjan min-cost circulation algorithm

Lecture 5: Cancel-and-tighten algorithm; binary search trees

Lecture 6: Splay trees

Lecture 7: Dynamic trees (part 1)

Lecture 8: Dynamic trees (part 2)

Lecture 9: Linear programming (LP)

Lecture 10: LP: duality, geometry, simplex

Lecture 11: LP: complexity; introduction to the ellipsoid algorithm

Lecture 12: LP: ellipsoid algorithm

Lecture 13: LP: applications of the ellipsoid algorithm

Lecture 14: Conic programming I

Lecture 15: Conic programming II

Lecture 16: Approximation algorithms

Lecture 17: Approximation algorithms (facility location)

Lecture 18: Approximation algorithms (max-cut)

Lecture 19: Max-cut and sparsest-cut

Lecture 20: Multi-commodity flows and metric embeddings

Lecture 21: Convex hulls

Lecture 22: Convex hulls and fixed dimension LP

Lecture 23: Voronoi diagrams

Lecture 24: Approximation scheme for the Euclidean traveling salesman problem

Lecture 25: Streaming algorithms

Lecture 26: Streaming algorithms (cont’d)