6.856
Randomized Algorithms
Fall 2002
Topics
- Introduction to Randomized Algorithms
- Min-Cut, Complexity Theory, Game Tree Evaluation
- Adelman’s Theorem, Game Theory, Lower Bounds
- Coupon Collecting, Stable Marriage, Markov Inequality
- Chebyshev, Two Point Sampling, Chernoff
- Median Finding, Routing
- Probabilistic Method, Expanders, Wiring, MAX SAT
- Method of Conditional Probabilities and Expectations, Fingerprinting
- Hashing, Perfect Hash Families, Freivald’s Technique
- Fingerprints by Polynomials, Perfect Matching, Hashing
- Shortest Paths
- Parallel Algorithms
- Maximal Independent Sets
- Minimum Spanning Trees
- Polling, Minimum Cut, Transitive Closure
- Estimating Min-Cut Size
- Linear Programming
- DNF Counting
- Markov Chains
- UTS, Eigenvalue Analysis, Expanders
- Expander based Pseudo-Random Generator
- Sampling with Markov Chains, Coupling
- Computational Geometry
- Randomized Incremental Construction
- Trapezoidal Decomposition, Treaps
- Online Algorithms
Readings
- Read a new (not yet textbook) algorithm from the recent research literature, and improve upon it in via some mixture of the following:
- Use a randomized algorithm or technique to solve a problem drawn from your own research area. The randomized algorithm may be classical (textbook) if it is applied in a novel manner. Alternatively, you may need to develop a new randomized algorithm to solve your problem. Considerations are similar to those for a basic implementation project above.
Sources
- Course catalogue ↗Historical OpenCourseWare
- MIT OCW syllabus ↗
- MIT OCW calendar ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.