Lecture Notes on Randomized Algorithms


A course on randomized algorithms taught at Dartmouth.

  1. Introduction, Equality Testing, Monte Carlo Algorithms
  2. Linearity of Expectation, QuickSort, Las Vegas Algorithms
  3. Karger’s Minimum Cut Algorithm
  4. EstimationAlgorithms, Chebyshev, Chernoff-Hoeffding Bound
  5. Median of Means Proof, More General Chernoff Bounds
  6. Randomized Median Finding
  7. Estimating #DNF : Importance Sampling
  8. Finding Similar Pairs via Importance Sampling
  9. How to Sample in Importance Sampling?
  10. Estimating the Average Degree in an Undirected Graph
  11. Balls and Bins I : Birthday Paradox, Max Load, and Collect- ing Coupons
  12. Balls and Bins II : Poisson Random Variables and Poisson Ap- proximation
  13. Hashing I : Universal Hash Functions
  14. Hashing II : Fingerprinting
  15. Hashing III : Perfect Hashing
  16. Hashing IV : Locality Sensitive Hashing and Nearest Neighbors
  17. Dimension Reduction and the Johnson-Lindenstrauss Lemma
  18. Streaming I : Frequency Estimation via Count-Min
  19. Streaming II : Count Sketch and Estimating Second Frequency Moment .
  20. Streaming III : Estimating F_k and Reservoir Sampling
  21. Streaming IV : Counting Distinct Elements
  22. Streaming V : Counting Distinct Elements II
  23. Streaming VI : Counting Distinct Elements with Deletions
  24. Experts Problem : Multiplicative Weight Updates
  25. Experts Problem : Follow the Perturbed Leader
  26. Randomization for Approximation Algorithms
  27. k-means++ Algorithm for Clustering
  28. A Lecture on Derandomization