Randomized Algorithms

• Randomized Algorithms. Motwani, R. and Raghavan, P., Cambridge University Press, 1995. [cover]
• Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Second Edition. M. Mitzenmacher and E. Upfal, Cambridge University Press, 2017. [cover]

• Attendance (10%)
• Quizzes and Assignments (60%)
• Final Exam/ Paper Presnetation (30%)

1. Introduction & the Min-Cut Problem [slides; updated 2 March 2026]
2. Discrete Random Variables and Expectations [slides; updated 2 March 2026]
3. Randomized QuickSort & k-Smallest Number Selection [slides; updated 2 March 2026]
4. Complexities [slides; updated 17 March 2026]
5. Minimax Principles [slides; updated 17 March 2026]
6. Coupon Collector's Problem and Conditional Expectation [slides; updated 5 May 2026]
7. The Secretary Problem [slides; updated 31 March 2026]
8. Moments and Deviations [slides; updated 28 March 2026]
9. Randomized Median Selection: A Sampling-Based Approach [slides; updated 14 April 2026]
10. Chernoff & Hoeffding Bounds [slides; updated 6 June 2026]
11. Balls and Bins [slides; updated 21 April 2026]
12. The Poisson Approximation [slides; updated 28 April 2026]
13. Random Graphs [slides; updated 28 April 2026]
14. Markov Chains and Random Walks [slides; updated 31 May 2026]
15. Randomized 2-SAT and 3-SAT Algorithms [slides; updated 9 May 2026]
16. Random Walks on Undirected Graphs [slides; updated 17 May 2026]
17. Continuous Distributions and the Poisson Process [slides; updated 21 May 2026]
18. The Probabilistic Method [slides; updated 26 May 2026]
19. Lovász Local Lemma and Applications [slides; updated 26 May 2026]
20. The Monte Carlo Method [slides; updated 1 June 2026]
21. Other Selected Topics

• Exercise Set 1 [pdf]
• Exercise Set 2 [pdf]
• Exercise Set 3 [pdf]
• Exercise Set 4 [pdf]
• Final Exam [pdf]

© 2004 Joseph Chuang-Chieh Lin