CS590R: Randomized Algorithms and Probabilistic Techniques in CS- Spring 2004

Professor

Gopal Pandurangan
Office: CS 128
Office hours: by appointment

Lectures

Tue, Thu: 10.30-11:45am; Room: CS G066

About this course

Probabilistic techniques, in general, and randomized algorithms, in particular, play an increasingly important role in a variety of computer science applications ranging from cryptography and communication networks to Web search engines, AI reasoning, data mining, and bioinformatics.

This course will serve as an introduction to probability theory in computer science, in particular to randomized algorithms and to probabilistic analysis of algorithms. The course introduces basic probability theory and presents applications of randomized algorithms and probabilistic analysis techniques in areas such as combinatorial optimization, data structures, graph algorithmics, communication, parallel and distributed computation, cryptography, biology and more.

Assumes no prior knowledge of probability theory. Prerequisite is (at least) an undergraduate course in algorithms or approval by instructor.

Textbooks

1. Probabilistic Analysis and Randomized Algorithms by M. Mitzenmacher and E. Upfal. (Required -- Available from Copymat, Chauncey Mall)
2. Randomized Algorithms by R. Motwani and P. Raghavan. (Recommended)
3. A First Course in Probability by S. Ross. (Useful reference for Probability)
4. Probability and Random Processes by G. Grimmett and D. Stirzaker (reference for more advanced concepts in probability)

Newsgroup

We plan to use the purdue.class.cs590r newsgroup (on the server news.purdue.edu) for announcements and other postings. You should subscribe to this newsgroup and check it regularly. Send all general questions (such as clarifications regarding assignments etc.) to this newsgroup.

WebCT

We will use WebCT to turn in assignments.