# Randomized Algorithms: Fall 2012

## People

 Dr. S. Rao Kosaraju - Instructor P.C. Shyamshankar (Shyam) - TA

## Dates & Times

Class
Tuesdays & Thursdays, 13:30 to 14:45, at Shaffer 302.
TA Office Hours
Mondays 13:00, at Shaffer 201.
Mid-Term Exam
Thursday, October 25th 2012, 13:30 to 14:45 (during class), at Shaffer 302.
Final Exam
Friday, December 14th 2012, 9:00 to 12:00, at Shaffer 302.

## Assignments

 Assignment #01 Due: 09/13 Problems Solutions Assignment #02 Due: 09/20 Problems Solutions Assignment #03 Due: 10/04 Problems Solutions Assignment #04 Due: 10/11 Problems Solutions Assignment #05 Due: 10/18 Problems Solutions Mid-Semester Exam In class, 10/25 Problems Solutions Assignment #06 Due: 10/30 Problems Solutions Assignment #07 Due: 11/08 Problems Solutions Assignment #08 Due: 11/29 Problems Solutions

## Resources

### Textbook

The textbook for this course is Probability and Computing: Randomized Algorithms and Probabilistic Algorithms, by Michael Mitzenmacher and Eli Upfal.

### Topics

This course emphasizes how randomization can be a useful tool in algorithmic design. We expect to cover some of the following topics:
• Random Variables, and k-wise independence;
• Tail Inequalities - The Markov, Chebyshev and Chernoff Bounds;
• Design of simple randomized Algorithms;
• Linear Programming Relaxation and Randomized Rounding;
• Derandomization:
• The Conditioning Method;
• The Limited Independence Method;
• The Log-Space Verification Method;
• Existence Proofs;
• Universal Hashing
• Markov Chain Mixing:
• The Metropolis and Metropolis-Hastings Algorithms;
• The Coupling Method;
• The Eigenvalue Method;
• Counting Problems;
• Semi-Definite Programming;
• Lower Bound Arguments;
• Random Bit Generation;
• Appications of Expanders.

### Exams

 Fall 2011: Mid-Semester Fall 2010: Mid-Semester Spring 2010: Mid-Semester Fall 2011: Final