1
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.
FREE
This course includes
Hours of videos
694 years, 4 months
Units & Quizzes
25
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
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 Currilcum
- 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
