Randomized Algorithms

Lecture Notes

LEC #	TOPICS
1	Introduction to Randomized Algorithms (PDF)
2	Min-Cut, Complexity Theory, Game Tree Evaluation (PDF)
3	Adelman's Theorem, Game Theory, Lower Bounds (PDF)
4	Coupon Collecting, Stable Marriage, Markov Inequality (PDF)
5	Chebyshev, Two Point Sampling, Chernoff (PDF)
6	Median Finding, Routing (PDF)
7	Probabilistic Method, Expanders, Wiring, MAX SAT (PDF)
8	Method of Conditional Probabilities and Expectations, Fingerprinting (PDF)
9	Hashing, Perfect Hash Families, Freivald's Technique (PDF)
10	Fingerprints by Polynomials, Perfect Matching, Hashing (PDF)
11	Shortest Paths (PDF)
12	Parallel Algorithms (PDF)
13	Maximal Independent Sets (PDF)
14	Minimum Spanning Trees (PDF)
15	Polling, Minimum Cut, Transitive Closure (PDF)
16	Estimating Min-Cut Size (PDF)
17	Linear Programming (PDF)
18	DNF Counting (PDF)
19	Markov Chains (PDF)
20	UTS, Eigenvalue Analysis, Expanders (PDF)
21	Expander based Pseudo-Random Generator (PDF)
22	Sampling with Markov Chains, Coupling (PDF)
23	Computational Geometry (PDF)
24	Randomized Incremental Construction (PDF)
25	Trapezoidal Decomposition, Treaps (PDF)
26	Online Algorithms

Assignments