Open Course Space

Randomized Algorithms

Massachusetts Institute of TechnologyUnited States6.856J
Free, no sign-up neededFall 2002English
Go to course on MIT OpenCourseWare

This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Topics covered include: randomized computation; data structures (hash tables, skip lists); graph algorithms (minimum spanning trees, shortest paths, minimum cuts); geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension); approximate counting; parallel algorithms; online…

Description from MIT OpenCourseWare.

Where to take this course