0
(
ratings
)
1
students
Created by:
Last updated:
September 7, 2022
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains.
Topics covered include: 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; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms.
Course Curriculum
- Introduction to Randomized Algorithms Unlimited
- Min-Cut, Complexity Theory, Game Tree Evaluation Unlimited
- Adelman’s Theorem, Game Theory, Lower Bounds Unlimited
- Coupon Collecting, Stable Marriage, Markov Inequality Unlimited
- Chebyshev, Two Point Sampling, Chernoff Unlimited
- Median Finding, Routing Unlimited
- Probabilistic Method, Expanders, Wiring, MAX SAT Unlimited
- Method of Conditional Probabilities and Expectations, Fingerprinting Unlimited
- Hashing, Perfect Hash Families, Freivald’s Technique Unlimited
- Fingerprints by Polynomials, Perfect Matching, Hashing Unlimited
- Shortest Paths Unlimited
- Parallel Algorithms Unlimited
- Maximal Independent Sets Unlimited
- Minimum Spanning Trees Unlimited
- Polling, Minimum Cut, Transitive Closure Unlimited
- Estimating Min-Cut Size Unlimited
- Linear Programming Unlimited
- DNF Counting Unlimited
- Markov Chains Unlimited
- UTS, Eigenvalue Analysis, Expanders Unlimited
- Expander based Pseudo-Random Generator Unlimited
- Sampling with Markov Chains, Coupling Unlimited
- Computational Geometry Unlimited
- Randomized Incremental Construction Unlimited
- Trapezoidal Decomposition, Treaps Unlimited
About the instructor
5
5
Instructor Rating
1
Reviews
1520
Courses
1916
Students
Massachusetts Institute of Technology
