6.5220J / 18.416J Randomized Algorithms
Repeats every week every Monday and every Wednesday and every Friday until Wed Dec 10 2025 except Fri Sep 19 2025, Mon Oct 13 2025, Mon Nov 10 2025, Fri Nov 28 2025.
Wed, 09/03/2025 - 2:30pm to 4:00pmLocation:
32-123
Instructor:
David Karger
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.