CSE 525: Randomized Algorithms and Probabilistic Analysis (SP 07)

[course description | lectures | assignments | related material]

course description

Instructor: James Lee, CSE 640, tel. 616 4368
Office hours: Tuesdays and Thursdays, 4:30-5:30pm, or by appointment

Teaching assistant: Ning Chen, CSE 310
Office hours: Thursdays at 4:30pm

Classes are Tuesdays and Thursdays, 10:30-11:50am, EEB 025

Course evaluation: Bi-weekly homeworks and a final exam.

About this course:
Randomization and probabilistic analysis have become fundamental tools in modern Computer Science, with applications ranging from combinatorial optimization to machine learning to cryptography to complexity theory to the design of protocols for communication networks. Often randomized algorithms are more efficient, and conceptually simpler and more elegant than their deterministic counterparts.

We will cover some of the most widely used techniques for the analysis of randomized algorithms and the behavior of random structures from a rigorous theoretical perspective. A (non-random) sample of topics to be covered includes elementary examples like randomized pattern matching and primality testing, large-deviation inequalities, the probabilistic method, martingales, random graphs, random geometric algorithms, and the analysis of Markov chains. Tools from discrete probability will be illustrated via their application to problems like randomized rounding, hashing of high-dimensional data, and load balancing in distributed systems.

schedule of classes

1. March 27 Introduction to randomness in computation; types of randomized algorithms; identity checking.
2. March 29 Polynomial identity testing; testing for perfect matchings; fingerprints, hashing, and pattern matching.
3. April 3 Linearity of expectation, Markov's inequality, the probabilistic method; monotone circuits for majority.
4. April 5 Variance, Chebyshev's inequality; random graphs and threshold phenomena.
5. April 10 The Laplace transform and Hoeffding-Azuma-Chernoff bounds; randomized routing on the hypercube.
6. April 12 Randomized routing continued.
7. April 17 Randomized rounding of linear programs; disjoint paths in directed graphs.
8. April 19 Balls in bins and the power of two choices.
9. April 24 Geometric concentration, random projections, dimension reduction.
10. April 26 Nearest-neighbor search in high-dimensional spaces.
11. May 1 The Lovasz Local Lemma.
12. May 3 Geometric applications of the local lemma.
13. May 8 Martingales, Azuma's inequality, and applications.
14. May 10 Some foundations of discrete probability.
15. May 15 Exposure martingales in graphs; random geometric TSP.
16. May 17 The optional stopping theorem and 2-SAT with random walks.
17. May 22 Random walks on graphs: cover and hitting times.
18. May 24 NO CLASS
19. May 29 Markov chain Monte Carlo
20. May 31 MCMC continued

related material

Courses at other schools:

• Lecture notes by Avrim Blum at CMU.
• Lecture notes by David Karger at MIT.
• Lecture notes by Anupam Gupta and Shuchi Chawla at CMU.

Suggested references:

• The Probabilistic Method by Alon and Spencer.
• Probability and Random Processes (2nd ed.) by Grimmett and Stirzaker.
• Randomized Algorithms by Motwani and Raghavan.

assignments