CPS237

 

Spring 2008

 

RANDOMIZED ALGORITHMS


Class Schedule and Class Notes


Course Synopsis

Randomized Algorithms. Models of computation, Las Vegas and Monte Carlo algorithms, linearity of expectation, Markov and Chebyshev inequalities and their applications, Chernoff bound and its applications, probabilistic methods, expanders,random walks and rapidly mixing Markov chains. Randomized algorithms for data structures, graph problems, geometric problems,  online problems, approximation, computational algebra, number theory and cryptography.

Course Topics

1.    Introduction: Examples of randomized algorithms: quicksort, BSP, mincut, partitioning, secretly computing an average, verifying matrix product, k-wise independence.

2.    Randomized Complexity Theory. models of randomized computation, Las Vegas and Monte Carlo algorithms, complexity classes, derandomization, discrepancy

3.    Randomized Games: Introduction to Game Theory and Equilibria. Game-Theoretic Models of Computation, min-max principle, and applications.

4.    Probability Moments and Tail Bounds: Linearity of expectation, Markov and Chebyshev inequalities, occupancy problem, randomized selection, coupon collector's problem

5.    Probabilistic methods: random graphs, expanders, and Lovasz local lemma.

6.    Randomized Data structures. Randomized search trees, universal hashing, and skip lists.

7.    Randomized Algebraic Methods: Hashing and Fingerprinting Polynomials. Applications to perfect matching and string searching.

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

9.    Randomized Geometric algorithms. Applications of random sampling of geometric objects, randomized incremental algorithms, and linear programming

10.Markov Chains and Random Walks. Markov chains, random walks, electric networks, rapidly mixing Markov chains, random walks on expanders. Applications to Approximate counting, approximating the permanent, and volume estimation

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

12.Randomized Parallel and Distributed Algorithms: Parallel Sorting, randomized distributed communication

13.Randomized Number Theory Algorithms: Number Theoretic rings and fields, integer factoring and primality testing.

14.Quantum Computation: Brief overview of quantum computing, quantum gates, and quantum algorithms.


Instructor

John H. Reif, Professor of Computer Science


Class Meetings

The following two days per week (see schedule):

   Monday 1:00 PM- 2:30 PM

   Wednesday 1:00 PM- 2:30 PM

    Friday 1:00 PM- 2:30 PM

Place: North Building, Room 306


Background

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


Textbooks

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

Errata

[MU] Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Published by Cambridge University Press, ISBN: 0521835402, Paperback, 352 pages, December 2004.


Prerequisites

CPS 230 or equivalent.


Grading

Class grade will be based on: