MIT Subject Listing & Schedule
Fall 2025 Search Results

Searched for:

1 subject found.

6.5220[J] Randomized Algorithms

()
(Same subject as 18.416[J])
Prereq: (6.1200 or 6.3700) and (6.1220 or 6.5210)
Units: 5-0-7
Lecture: MWF2.30-4 (32-123)

Studies how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Models of randomized computation. Data structures: hash tables, and skip lists. Graph algorithms: minimum spanning trees, shortest paths, and minimum cuts. Geometric algorithms: convex hulls, linear programming in fixed or arbitrary dimension. Approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms.
D. Karger
No textbook information available