Randomized Algorithms, Fall 2002
| Rating: | Not rated yet |
| Rate item | |
| Type: | Course Related Materials |
| Grade Level: | Post-secondary |
Author: Karger, David
Subject: Science and Technology
Institution Name:
M.I.T.
Collection Name: MIT OpenCourseWare
Abstract: 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.
Details
Course Type: Full Course
Material Types: Homework and Assignments, Lecture Notes, Syllabi
Media Formats: Text/HTML, Downloadable docs
Language: English
Additional Information
Geographic
Regional Relevance: All
