Seminar: Probability and Computing - Randomized Algorithms and Probabilistic Analysis

Term: Spring 2008
Time: Fri 12:00pm - 1:15pm
Location: HEC356

Instructor: Dr. Pawel Wocjan
Office hours: Tues & Thurs 2:30om - 3:45pm

Syllabus

Required Text:
The required text for the class is Probability and Computing: Randomized Algorithms and Probabilistic Analysis , by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. It is essential that all students have access to this book. Pointers to the relevant sections of the book will be provided as we go along. (see here for errata in the first printing of the book, some of which were corrected in the second printing.)

Objectives:
This seminar is a direct continuation of the introductory course "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" (taught as EEL6558 in Fall 2007) that is based on the first seven chapters of the Mitzenmacher/Upfal text. In this seminar, we will cover the more advanced material in Chapters 2 - 7 that was left out in that course and also new material in Chapters 8 and 10 - 14. We will also use the book "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan for additional algorithms, examples, and techniques. The pace of this seminar will be much faster than that of the introductory course and you will be required to do a lot of reading on your own!!!

The topics that will be covered are:

Overview of Randomized Complexity Classes
(Chapter 1; Motwani/Raghavan)
Game-Theoretic Techniques
(Chapter 2; Motwani/Raghavan)
Expander Graphs
(Chapter 6; Motwani/Raghavan)
The Monte Carlo Method
(Chapter 10; Mitzenmacher/Upfal)
Coupling of Markov Chains
(Chapter 11; Mitzenmacher/Upfal)
Martingales
(Chapter 12; Mitzenmacher/Upfal)
Pairwise Independence & Universal Hash Functions
(Chapter 13; Mitzenmacher/Upfal)
Balanced Allocations
(Chapter 14; Mitzenmacher/Upfal)
Continuous Distributions & the Poisson Process
(Chapter 8; Mitzenmacher/Upfal)

The material in Chapter 9 "Entropy, Randomness, and Information" in the Mitzenmacher/Upfal text will be covered as part of the course COT6602 "Quantum Information Theory".

Prerequisites:
COT 5405 Design and Analysis of Algorithms and EEL6558 (Probability and Computing in Fall 2007)

Grading Policy:
If you want to receive a grade for this seminar, you will have to register for an independent study with me.

Lectures

The following is a list of topics covered in each lecture, together with pointers to the corresponding portions of the Mitzenmacher/Upfal text, Motwani/Raghavan text, and where appropriate, additional lecture notes.

	Topic	Readings	Notes
Lecture #1 (01/11)	Markov Chains and Random Walks Markov Chains: Definitions and Representations Application: Randomized Algorithms for 2-SAT and 3-SAT	MU Sections 7.2 and 7.3
Lecture #2 (01/18)	Classification of States Stationary Distributions Example: A Simple Queue	Read MU Sections 7.4 and 7.5
Lecture #3 (01/25)	Random Walks on Undirected Graphs Application: An s-t Connectivity Algorithm Parrondo's Paradox	Motwani/Raghavan Sections 6.1 - 6.6 and Sections 5.3, 6.7, and 6.8 We have already covered the material in MR Sections 6.1 - 6.6 using the MU book. Expander graphs are introduced in MR Sections 5.3, 6.7, and 6.8.