Home » Course Layouts » Free Course Layout Udemy
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.
0
1
English
English [CC]
FREE
- Learn basic syntax that can apply to any language.
- Learn what is a programming language and the basic concepts for beginners.
- Understand what is Javascript in it's truest form.
- Know the basic syntax of Javascript.
- Know some hidden quirks in Javascript.
Description
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 content
- 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
Instructor
Massachusetts Institute of Technology
5
5
1
1916
1520
