6.856J Randomized Algorithms


Class Info

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.

This class has 6.854J, 6.041, and 6.042J as prerequisites.

6.856J will not be offered this semester. It will be available in the Spring semester, and will be instructed by D. R. Karger.

This class counts for a total of 12 credits. This is a graduate-level class.

In the Spring 2013 Subject Evaluations, 6.856J was rated 5.9 out of 7.0. You can find more information at the 6.856J/18.416J Randomized Algorithms site.

MIT 6.856J Randomized Algorithms Related Textbooks
MIT 6.856J Randomized Algorithms On The Web
6.856J/18.416J Randomized Algorithms
Tags
lecture edu link algorithms randomized Chebyshev Noble Markov Advanced Algorithms

© Copyright 2015