0

(

ratings

)

1

students

Created by:

Profile Photo

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

1915

Students

Profile Photo
Massachusetts Institute of Technology