• No products in the cart.

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.


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.


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
Submit Your Assignment 00:00:00
Certification 00:00:00

Course Reviews


8 ratings
  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course.

©2021 Edukite. All Rights Resereved
Edukite is A Part Of Ebrahim College, Charity Commission
Reg No 110841