MIT OpenCourseWare

Browse materialsMIT 6.856J · Fall 2002

Randomized Algorithms

Subject: Mathematics

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

Instructor: Prof. David R. Karger
Term: Fall 2002
Level: Graduate
What's inside: 1 lecture note · 51 other files · 3 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: Introduction to Randomized Algorithms Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 6.856J Randomized Algorithms, Fall 2002, 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 13 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 26 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

2 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.
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

25 files

Assignments

26 files

MIT OpenCourseWare, Prof. David R. Karger, 6.856J Randomized Algorithms, Fall 2002.

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

Randomized Algorithms

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Lecture 1: Introduction to Randomized Algorithms

Lecture 2: Min-Cut, Complexity Theory, Game Tree Evaluation

Lecture 3: Adelman’s Theorem, Game Theory, Lower Bounds

Lecture 4: Coupon Collecting, Stable Marriage, Markov Inequality

Lecture 5: Chebyshev, Two Point Sampling, Chernoff

Lecture 6: Median Finding, Routing

Lecture 7: Probabilistic Method, Expanders, Wiring, MAX SAT

Lecture 8: Method of Conditional Probabilities and Expectations, Fingerprinting

Lecture 9: Hashing, Perfect Hash Families, Freivald’s Technique

Lecture 10: Fingerprints by Polynomials, Perfect Matching, Hashing

Lecture 11: Shortest Paths

Lecture 12: Parallel Algorithms

Lecture 13: Maximal Independent Sets

Lecture 14: Minimum Spanning Trees

Lecture 15: Polling, Minimum Cut, Transitive Closure

Lecture 16: Estimating Min-Cut Size

Lecture 17: Linear Programming

Lecture 18: DNF Counting

Lecture 19: Markov Chains

Lecture 20: UTS, Eigenvalue Analysis, Expanders

Lecture 21: Expander based Pseudo-Random Generator

Lecture 22: Sampling with Markov Chains, Coupling

Lecture 23: Computational Geometry

Lecture 24: Randomized Incremental Construction

Lecture 25: Trapezoidal Decomposition, Treaps

Lecture 26: Online Algorithms