# 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