The course with the Cockertoo...

Randomized Algorithms

CPSC 689, Course Information, Spring 2006

The course gives an introduction to randomized algorithms. Randomization allows to design efficient algorithms, which are often of elegant simplicity. Selected tools and techniques from probability theory and game theory are reviewed, with a view towards algorithmic applications. The main focus is a thorough discussion of the main paradigms, techniques, and tools in the design and analysis of randomized algorithms. A detailed analysis of numerous algorithms will illustrate the abstract concepts and techniques. You will learn about random walks, Markov chains, the probabilistic method, discrepancy theory, etc. The basics of probability theory will be reviewed.

Instructor Dr. Andreas Klappenecker,
Office HRBB 509B,
Office hours TBD

General Information

Lecture Notes

Homework

Schedule

T Jan 17 Events, probabilities, minimum cut; read [MU,Chapter 1]
R Jan 19 Contraction algorithm, fingerprinting; read lecture notes §2.1
T Jan 24 Random variables, expectation, randomized quicksort
R Jan 26 Binomial and geometric distributions, coupon collector problem
T Jan 31 Iverson notation, conditional expectation
R Feb 02 Markov's and Chebychev's inequality, variance
T Feb 07 Randomized median algorithm
R Feb 09 Chernoff inequalities, set balancing, moment generating functions
T Feb 14 Packet routing in the hypercube
R Feb 16 Birthday paradox, balls and bins
T Feb 21 Balanced allocations, hashing
R Feb 23 Bloom filters
T Feb 27 Poisson distribution, Poisson approximation

Literature

Good survey article: Some journals and conferences that will be used during this course: Some works of your colleagues: