CS590R: Randomized Algorithms and Probabilistic Techniques in CS - Fall 2005

Professor

Gopal Pandurangan
Office: CS 128
Office hours: by appointment

Lectures

Tue, Thu: 3-4.15 pm; Room: CIVL 2107

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, data mining, and bioinformatics. In fact, here is what Donald Knuth has to say on what was the most important change in the study of algorithms in recent years: "... randomized algorithms had to be the winner ..." (audio).

This course will serve as an introduction to randomized algorithms and to probabilistic analysis of algorithms. The course introduces probabilisitic tools and techniques (which should be in the arsenal of every computer science grad student) and presents applications of randomized algorithms and probabilistic analysis techniques in areas such as combinatorial optimization, data structures, graph algorithmics, communication, networking, parallel and distributed computation, computational biology/bioinformatics and more.

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

Lecture Notes

Lecture 1: 1.pdf
Lecture 2: 2.pdf
Lecture 3: 3.pdf
Lecture 4: 4.pdf
Lecture 5: 5.pdf
Lecture 6: 6.pdf
Lecture 7: 7.pdf
Lecture 8: 8.pdf
Lecture 9: 9.pdf
Lecture 10: 10.pdf
Lecture 11: 11.pdf
Lecture 12: 12.pdf
Lecture 13: 13.pdf
Lecture 14: 14.pdf
Lecture 15: 15.pdf
Lecture 16: 16.pdf
Lecture 17: 17.pdf
Lecture 18: 18.pdf
Lecture 19: 19.pdf
Lecture 20: 20.pdf
Lecture 21: 21.pdf
Lecture 22: 22.pdf
Lecture 23: 23.pdf
Lecture 24: 24.pdf
Lecture 25: 25.pdf
Lecture 26: 26.pdf
Lecture 27: 27.pdf
Lecture 28: 28.pdf

Textbooks

1. Probability and Computing by M. Mitzenmacher and E. Upfal. (required)
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.