MIT OpenCourseWare

Browse materialsMIT 6.854J · Fall 2005

Advanced Algorithms

Subject: Mathematics

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

Instructor: Prof. David R. Karger
Term: Fall 2005
Level: Graduate
What's inside: 1 lecture note · 1 reading · 95 other files · 4 web pages
Materials open: MIT OCW

Other versions of this course

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

Start here

Start course: Lecture 1: Course Introduction 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 2005, Prof. David R. Karger — 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 12 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

A lecture sequence of 29 items is confirmed. Assignment and exam materials exist too, but MIT's own order for them could not be verified, so they're shown as materials below rather than a sequence.

Not included here

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

Materials by section

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

Lecture Notes

38 files

Assignments

23 problem sets

Other materials from this course

34 files

MIT OpenCourseWare, Prof. David R. Karger, 6.854J Advanced Algorithms, Fall 2005.

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

Other materials from this course

Lecture 1: Course Introduction Fibonacci Heaps

Lecture 2: MST Persistent Data Structures

Lecture 3: Splay Trees

Lecture 4: Splay Trees (cont.) Suffix Trees Tries

Lecture 5: Suffix Trees (cont.) Tries (cont.) Dial’s Algorithm

Lecture 6: Dijkstra’s Algorithm Van Emde Boas Queues

Lecture 7: Van Emde Boas Queues (cont.) Hashing

Lecture 8: 2-Level Hashing Network Flows

Lecture 9: Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling

Lecture 10: Reductions between Flow Problems Bipartite Matching Shortest Augmenting Path Blocking Flows

Lecture 11: Blocking Flows (cont.)

Lecture 12: Min-Cost Flows

Lecture 13: Min-Cost Flows (cont.) Linear Programming

Lecture 14: Linear Programming (cont.) Structure of Optima Weak Duality

Lecture 15: Linear Programming (cont.) Strong Duality

Lecture 16: Linear Programming (cont.) Complementary Slackness Algorithms: Simplex, Ellipsoid

Lecture 17: Linear Programming (cont.) Algorithms: Interior Point NP-hard problems

Lecture 18: Approximation Algorithms

Lecture 19: 4/3-Approximation for TSP

Lecture 20: Relaxations Directed TSP

Lecture 21: Randomized Rounding Chernoff Bound Fixed Parameter Tractability Kernelization

Lecture 22: Online Algorithms (Ski Rental, Load Balancing, Paging)

Lecture 23: Randomized Online Algorithms (Adversaries, Fiat’s Marking Algorithm, Potential Functions, Yao’s Minimax Principle)

Lecture 24: K-Server Problem Double-Coverage Algorithm Computational Geometry Introduction (Orthogonal Range Search)

Lecture 25: Sweep Algorithms (Convex Hull, Segment Intersection, Voronoi Diagrams)

Lecture 26: Sweep Algorithms (Voronoi Diagrams) Randomized Incremental Constructions Backwards Analysis Linear Programming in Fixed Dimension

Lecture 27: (Optional Material) External Memory Algorithms

Lecture 28: (Optional Material) Cache Oblivious Algorithms: Matrix Multiplication, Linked Lists, Median

Lecture 29: (Optional Material) Cache Oblivious Algorithms: Search Streaming Model