CPS237

 

Fall 2003

 

RANDOMIZED ALGORITHMS


Class Schedule and Class Notes


Course Synopsis

1.     Introduction. Examples of randomized algorithms, models of computation, Las Vegas and Monte Carlo algorithms, complexity classes, min-max principle.

2.     Moment and deviation. Linearity of expectation, Markov and Chebyshev inequalities, occupancy problem, randomized selection, coupon collector's problem

3.     Tail inequalities. The Chernoff bound, routing and wiring problems

4.     Probabilistic methods. Deletion methods, random graphs, expanders, Lov\'{a}sz local lemma

5.     Derandomization. k-wise independence, probabilistic methods, discrepancy, derandomization in parallel

6.     Data structures. Randomized search trees, hashing, skip lists;

7.     Graph algorithms. Shortest paths, minimum spanning trees, Min cut, independent sets, dynamic graph algorithms

8.     Geometric algorithms. Random sampling, randomized incremental algorithms, linear programming

9.     Markov Chains and Random Walks. Markov chains, random walks, electric networks, rapidly mixing Markov chains, random walks on expanders

10.  Approximate counting. Monte Carlo methods, approximating the permanent, volume estimation

11.  Online algorithms. Paging problem, $k$-server problem, adversary models

12.  Number theoretic algorithms. Groups and fields, quadratic residues, RSA cryptosystem, polynomial roots and factoring, primality testing


Instructor

John H. Reif, Professor of Computer Science


Class Meetings

The following two days per week (see schedule):

         Tuesday 3:50 PM-5:05 PM

        Thursday 3:50 PM-5:05 PM

 

Place: Levine Science Research Center(LSRC) Building Room D243 (changed from assigned room LSRC A158)


Background

The course provides an introduction to randomized algorithms and probabilistic analysis of algorithms.


Textbook

Rajeev Motwani  Prabhakar Raghavan, Randomized Algorithms, Published by Cambridge  University Press, ISBN: 0521474655, 492 pages. June  1995.


Prerequisites

CPS 230 or equivalent.


Grading

Class grade will probably be based on: