CSL866: Randomized Algorithms
II semester: 2007-08
Sandeep Sen and Amitabha Bagchi
Class Timings: Tu, W, F: 10AM to 10:55.
Room: 204 Bharti Building.
In class exam on Tuesday, 4th March 2008.
Overview
The objective of this class is to train students in the use of
randomization in the design of efficient algorithms for a range of
problems and also to teach them how to use to probability-based
techniques to analyze the complexity of certain classes of
algorithms.
Topics
Moments and deviations; Chernoff bounds; Occupancy problems; The
probabilistic method; Markov chains and random walks; Martingales;
Randomized Rounding; Hashing; Randomized data structures and geometric
algorithms; Approximation algorithms and approximate counting;
Randomized graph algorithms; Online algorithms.
Exams and homework assignments
- Homework 1. (ps, pdf). Due
before class on Friday, 8th February 2008.
- The airline seating puzzle.
- Homework 2. (ps, pdf). Due
before class on Tuesday, 11th March 2008.
- Homework 3. (ps, pdf). Due
before class on Friday, 11th April 2008.
Texts and notes
Students are not required to buy any text book.
- The primary text for this class will be
Probability and Computing by M. Mitzenmacher
and E. Upfal, Cambridge University Press, 2005.
- Another important text will be Randomized
Algorithms by R. Motwani and P. Raghavan,
Cambridge University Press, 1995. (Also available in an Indian
edition).
- Lecture notes for a simple proof (due to Satish Rao) for the "power of two choices" result. (ps, pdf).
Source: From a class taught by Amitabha Bagchi at UC, Irvine in 2004.
Evaluation
Sandeep Sen
Amitabha
Bagchi