CPS237

 

Spring 2002

 

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

Two of the following three days per week (see schedule; the updated times start 1/16/2002):

         Monday 3:45PM-5:00PM (officially listed as 3:55PM-5:10PM)

        Wednesday 10:25AM-11:40AM  (officially listed as 10:30AM-11:45AM)

         Friday 10:25AM-11:40AM  (officially listed as 10:30AM-11:45AM)

Place: Levine Science Research Center(LSRC) Building D243


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: