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). It also discusses geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension), approximate counting, parallel algorithms, online algorithms, and tools for probabilistic analysis of algorithms.
Assessment
This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer need to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.
Certification
Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.
Having an Official Edukite Certification is a great way to celebrate and share your success. You can:
- Add the certificate to your CV or resume and brighten up your career
- Show it to prove your success
Course Credit: MIT
Course Curriculum
| Module 01 | |||
| Introduction to Randomized Algorithms | 00:10:00 | ||
| Min-Cut, Complexity Theory, Game Tree Evaluation | 00:10:00 | ||
| Adelman’s Theorem, Game Theory, Lower Bounds | 00:10:00 | ||
| Coupon Collecting, Stable Marriage, Markov Inequality | 00:10:00 | ||
| Chebyshev, Two Point Sampling, Chernoff | 00:10:00 | ||
| Median Finding, Routing | 00:10:00 | ||
| Probabilistic Method, Expanders, Wiring, MAX SAT | 00:10:00 | ||
| Method of Conditional Probabilities and Expectations, Fingerprinting | 00:10:00 | ||
| Hashing, Perfect Hash Families, Freivald’s Technique | 00:10:00 | ||
| Fingerprints by Polynomials, Perfect Matching, Hashing | 00:10:00 | ||
| Shortest Paths | 00:10:00 | ||
| Parallel Algorithms | 00:10:00 | ||
| Module 02 | |||
| Maximal Independent Sets | 00:10:00 | ||
| Minimum Spanning Trees | 00:10:00 | ||
| Polling, Minimum Cut, Transitive Closure | 00:10:00 | ||
| Estimating Min-Cut Size | 00:10:00 | ||
| Linear Programming | 00:10:00 | ||
| DNF Counting | 00:10:00 | ||
| Markov Chains | 00:10:00 | ||
| UTS, Eigenvalue Analysis, Expanders | 00:10:00 | ||
| Expander based Pseudo-Random Generator | 00:10:00 | ||
| Sampling with Markov Chains, Coupling | 00:10:00 | ||
| Computational Geometry | 00:10:00 | ||
| Randomized Incremental Construction | 00:10:00 | ||
| Trapezoidal Decomposition, Treaps | 00:10:00 | ||
| Assessment | |||
| Submit Your Assignment | 00:00:00 | ||
| Certification | 00:00:00 | ||
Course Reviews
No Reviews found for this course.
