MIT Department of Electrical Engineering & Computer Science

E E C S

EECS Fall 1996 Catalogue Supplement

6.891 Randomized Algorithms (H)

TR 2:30-4, 37-186
3-0-9
Prof. David Karger, NE43-321, x8-6167
A study of how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, markov chains. Models of 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: perfect matchings, satisfying assignments; volume of convex bodies. Parallel algorithms: maximum independent sets, perfect matchings. Online algorithms: paging and scheduling, tools for probabilistic analysis of algorithms; tail inequalities, Chernoff bounds, martingales. Derandomized techniques: expanders, limited independence.
URL of this page: http://www-eecs.mit.edu/AY96-97/fall-cat/6891.html
Editor: Mibsy Brooks | Created: Jun 4, 1996 | Modified: Jun 4, 1996
Related page: EECS Fall 1996 Catalogue Supplement
To MIT EECS home page | Your comments and inquiries are welcome.