everything.study
18.416

Randomized Algorithms

5-0-7 units · Graduate

See description under subject 6.5220J.

Fall 2002

Topics

  • Introduction to Randomized Algorithms
  • Min-Cut, Complexity Theory, Game Tree Evaluation
  • Adelman’s Theorem, Game Theory, Lower Bounds
  • Coupon Collecting, Stable Marriage, Markov Inequality
  • Chebyshev, Two Point Sampling, Chernoff
  • Median Finding, Routing
  • Probabilistic Method, Expanders, Wiring, MAX SAT
  • Method of Conditional Probabilities and Expectations, Fingerprinting
  • Hashing, Perfect Hash Families, Freivald’s Technique
  • Fingerprints by Polynomials, Perfect Matching, Hashing
  • Shortest Paths
  • Parallel Algorithms
  • Maximal Independent Sets
  • Minimum Spanning Trees
  • Polling, Minimum Cut, Transitive Closure
  • Estimating Min-Cut Size
  • Linear Programming
  • DNF Counting
  • Markov Chains
  • UTS, Eigenvalue Analysis, Expanders
  • Expander based Pseudo-Random Generator
  • Sampling with Markov Chains, Coupling
  • Computational Geometry
  • Randomized Incremental Construction
  • Trapezoidal Decomposition, Treaps
  • Online Algorithms

Readings

  • Read a new (not yet textbook) algorithm from the recent research literature, and improve upon it in via some mixture of the following:
    Listed reading
  • Use a randomized algorithm or technique to solve a problem drawn from your own research area. The randomized algorithm may be classical (textbook) if it is applied in a novel manner. Alternatively, you may need to develop a new randomized algorithm to solve your problem. Considerations are similar to those for a basic implementation project above.
    Listed reading

Prerequisites & course information

Same subject as 6.5220J Prereq: ( 6.1200[J] or 6.3700 ) and ( 6.1220[J] or 6.5210[J] ) Acad Year 2027-2028: G (Fall) Acad Year 2028-2029: Not offered 5-0-7 units

Sources