Randomized Algorithms

This webpage serves as resources for studying randomized algorithms. Some slides here are modified from the lectures of Professor S.-C. Tsai and Professor H.-I. Lu.

Textbooks

Randomized Algorithms. Motwani, R. and Raghavan, P., Cambridge University Press, 1995. [cover]
Probability and Computing: Randomized Algorithms and Probabilistic Analysis. M. Mitzenmacher and E. Upfal, Cambridge University Press, 2005. [cover]
The Probabilistic Method. 2nd Edition. N. Alon and J. H. Spencer, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000. [cover]

Slides

* Note that you need to install TeX4PPT to view or edit the following powerpoint files.

Basic Probability Theory [zip]
Randomized Quicksort and the Max-cut problem
The Minimum Cut Problem
Las Vegas Algorithms, Monte Carlo Algorithms and Some Related Complexity Classes [ppt, pdf]
NOR-gates Evaluation Problem And the Minimax Principle
Selection by Sampling
The Stable Marriage Problem and the Coupon Collector's Problem [ppt, pdf]
Two-point Sampling [ppt, pdf]
The Chernoff Bounds for Analyzing Tail Probabilities [ppt, pdf]
Permutation Routing
Algorithms with Random Walks
Randomized Rounding and Approximation via Derandomization
Fingerprinting techniques
Solving the Minimum Spanning Tree Problem in Expected Linear Time
Randomized Balanced Search Trees
Randomized All-pairs Shortest Path
Markov Chains [ppt, pdf]
Parrondo Paradox [ppt, pdf]
Top-in Card Shuffling
Derandomizing Randomized Circuits and Adleman's Theorem
The Monte-Carlo Method [ppt, pdf]
Interactive Proof Systems
Introduction to Property Testing [ppt, pdf]
Introduction to the Regularity Lemma [pdf]

Selected exercises

Events and probability [pdf]
Discrete random variables and expectation [pdf]
Moments and deviations [pdf]
The Chernoff bounds [pdf]
Balls, bins, and random graphs [pdf]
The probabilistic method [pdf]

Any question is welcome.
Please contact Joseph, Chuang-Chieh Lin (Email to: josephcclin_AT_gmail_com)