Randomized Algorithms

This webpage provides textbooks, lectures and assignments of this course.

Textbooks

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]

Grading policy

Attendance (10%)
Assignments (30%)
Midterm Presnetation/Report (30%)
Final Paper Presentation (30%)

Lectures and assignments

Introduction & the Min-Cut Problem [slides]
Discrete Random Variables and Expectations [slides]
Randomized QuickSort & k-Smallest Number Selection [slides]
Complexities [slides]
Minimax Principles [slides]
Coupon Collector's Problem and Conditional Expectation [slides]
The Secretary Problem [slides]
Moments and Deviations [slides]
Chernoff & Hoeffding Bounds [slides]
Balls and Bins [slides]
Markov Chains and Random Walks [slides]
Continuous Distributions and the Poisson Process [slides]
Other Selected Topics

Please feel free to use the slides as long as giving appropriate credit to the author!
Any question is welcome.
Please contact Joseph, Chuang-Chieh Lin (Email to: josephcclin_AT_gms_tku_edu_tw)