CSE 525: Randomized Algorithms and Probabilistic Analysis (Spring 2013)

[course description | lectures | assignments | related material] | important announcements]

important announcements


Key (see references below): Scribe notes have NOT been vetted.


course description

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Time: Tuesdays and Thursdays in MGH 234, 10:30-11:50pm
Office hours:  By appointment -- send email.

Teaching assistant: Paris Koutris
Office hours:

Course evaluation: homework (~35%), scribe notes (~35%), and a final exam (~30%).

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 fingerprinting and minimum cut, large-deviation inequalities, the probabilistic method, martingales, random graphs, 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.

related material

Recommended text:
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.

Courses at other schools:

Suggested references: