The course with the Cockertoo...

Randomized Algorithms

CSCE 689, Course Information, Spring 2010

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

Syllabus

Required Textbook:

[MU] M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge University Press, 2005

Lecture Notes

Homework

Problem Set 1 due Monday, Feb 1.
Problem Set 2 due Monday, Feb 8.
Problem Set 3 due Monday, Feb 15.
Problem Set 4 due Monday, Mar 01.
Problem Set 5 due Monday, April 05.
Problem Set 6 due Monday, April 12 and Wednesday, April 14.

Schedule

W Jan 20 Introduction, Minimum Cut

F Jan 22 Sigma-Algebras, Probability Measures, Conditional Probability, Analysis of Minimum Cut

M Jan 25 Random Variables, Expectation

W Jan 27 Randomized Quicksort

F Jan 29 Markov's Inequality

M Feb 01 First Moment Method, Chebychev's Inequality, Covariance, Independence

W Feb 03 Geometric Random Variables, Randomized Median Finding

F Feb 05

M Feb 08

W Feb 10 Chernoff Bounds

F Feb 12 Chernoff Bounds, Set Balancing

M Feb 15 Packet Routing in the Hypercube

W Feb 17 Packet Routing in the Hypercube: Analysis

F Feb 19 Skip Lists

M Feb 22 Distributed Random Ranking, Euler's Summation Formula

M Mar 22 Probabilistic Method

W Mar 24 Local Lemma

F Mar 26 General Local Lemma

M Mar 29 Markov Chains, 2-SAT

W Mar 31 2-SAT, State Classification

F Apr 02 No class.

M Apr 05 Elephant and mice.

W Apr 07 Elephant and mice.

F Apr 09 Random walks.

Literature

A very good survey article:

R.M. Karp, An introduction to randomized algorithms, Discrete Applied Mathematics, 34, pp. 165-201, 1991.

Recommendations for Further Reading:

[MR] R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995
[DP] D.B. Dubhashi, A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2009
[AS] N. Alon, J. Spencer, The Probabilistic Method, 3rd edition, Wiley Interscience, 2008

Journals and Conferences:

W Jan 20	Introduction, Minimum Cut
F Jan 22	Sigma-Algebras, Probability Measures, Conditional Probability, Analysis of Minimum Cut
M Jan 25	Random Variables, Expectation
W Jan 27	Randomized Quicksort
F Jan 29	Markov's Inequality
M Feb 01	First Moment Method, Chebychev's Inequality, Covariance, Independence
W Feb 03	Geometric Random Variables, Randomized Median Finding
F Feb 05
M Feb 08
W Feb 10	Chernoff Bounds
F Feb 12	Chernoff Bounds, Set Balancing
M Feb 15	Packet Routing in the Hypercube
W Feb 17	Packet Routing in the Hypercube: Analysis
F Feb 19	Skip Lists
M Feb 22	Distributed Random Ranking, Euler's Summation Formula
M Mar 22	Probabilistic Method
W Mar 24	Local Lemma
F Mar 26	General Local Lemma
M Mar 29	Markov Chains, 2-SAT
W Mar 31	2-SAT, State Classification
F Apr 02	No class.
M Apr 05	Elephant and mice.
W Apr 07	Elephant and mice.
F Apr 09	Random walks.