main page — CS 627 Advanced Algorithms
Unit 9: Random Tricks
This unit covers algorithmic design techniques for randomized algorithms.
Material
- slides
- Video 9-1 (2025-06-25):
Random trick in Hashing
- Video 9-2 (2025-07-01):
Balls and bins
- Video 9-3 (2025-07-01):
Universal hashing
- Video 9-4 (2025-07-01):
Perfect hashing
- Video 9-5 (2025-07-02):
Perfect hashing analysis
- Video 9-6 (2025-07-02):
Primality testing
- Video 9-7 (2025-07-02):
Schönings SAT for 2SAT
Further reading and sources
- Motwani & Raghavan Randomized Algorithms (Cambridge University Press, 1995)
- Mitzenmacher & Upfal Probability and Computing (Cambridge University Press, 2005)