Instructors:

• Paul Beame
  • Office: Sieg 416
  • Email address: beame@cs.washington.edu
• Anna Karlin
  • Office: Sieg 426C
  • Email address: karlin@cs.washington.edu

Administrivia:

• Time: TTh 12:00-1:20
• Place: EE1 026
• Units: 3

Homework

• Homework # 1 (postscript)
• Homework # 2
• Homework # 3

Course Content:

This course will cover basic concepts in the design and analysis of randomized algorithms. We will attempt to emphasize mathematical techniques, recent results and current and future directions for research.

In addition to an overview of a number of randomized algorithms and techniques, a selection of the folllowing topics will be covered in greater depth:

• moments, deviations, tail inequalities
• the probabilistic method, including Lovasz Local Lemma and the method of conditional probabilities
• markov chains and random walks, applications to approximate counting, connections with eigenvalues
• random sampling, including applications in computational geometry, and graph algorithms (MST, Min-Cut, Flow, etc.)
• martingales, including application to computation of chromatic number of random graphs
• randomized rounding of integer and semi-definite programs.

Texts:

• R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press.
• Also recommended: N. Alon and J. Spencer, The Probabilistic Method , John Wiley and Sons.

Grading:

Each student will be expected to do problem sets, present a paper and attempt to come up with open problems. There will be no exams.