main page — CS 627 Advanced Algorithms
Unit 9: Random Tricks
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
This unit covers algorithmic design techniques for randomized algorithms.
Material
- slides
- Video 9-1 (2025-06-25, 18:33):
Random trick in Hashing
- Video 9-2 (2025-07-01, 45:58):
Balls and bins
- Video 9-3 (2025-07-01, 17:16):
Universal hashing
- Video 9-4 (2025-07-01, 15:12):
Perfect hashing
- Video 9-5 (2025-07-02, 11:52):
Perfect hashing analysis
- Video 9-6 (2025-07-02, 33:55):
Primality testing
- Video 9-7 (2025-07-02, 18:59):
Schöning’s SAT for 2SAT
- Video 9-8 (2025-07-08, 49:49):
Schöning’s 3SAT algorithm
Further reading and sources
- Motwani & Raghavan Randomized Algorithms (Cambridge University Press, 1995)
- Mitzenmacher & Upfal Probability and Computing (Cambridge University Press, 2005)