| Logistics: | TTh 11-12:30 TAY 3.144 Unique Number: 55853 Course web page: http://www.cs.utexas.edu/~diz/388R |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: TAY 3.134 Phone: 471-9729 Office Hours: TBD. |
| Texts: | Required:
R. Motwani and P. Raghavan,
"Randomized Algorithms".
This covers 80-90% of the course topics.
Highly Recommended: M. Mitzenmacher and E. Upfal, "Probability and Computing". This covers 40-50% of the course topics. It is targeted at a somewhat lower level than the required text, and should be particularly valuable for students without strong theory/math backgrounds. However, I highly recommend it for everybody. |
| Content: |
Randomness is extremely useful for developing
algorithms that are faster, and often simpler, than their
deterministic counterparts. In this course we will develop tools and
techniques for the design and analysis of efficient randomized
algorithms.
This course should be similar to the
2006 version.
A tentative list of topics follows.
Introduction: Quicksort, Min Cut, RP and BPP (1 week). Algebraic techniques: Fingerprinting, polynomials, primality testing (2-3 weeks). Probabilistic tools and techniques: Moments, tail inequalities, pairwise independence, randomized routing, occupancy problems, martingales, probabilistic method, isolation lemma and matching, random projection (4-5 weeks). Combinatorial optimization and approximation algorithms: Linear programming in small dimension, randomized rounding, semidefinite programming and Max Cut (2 weeks). Random walks and the Monte Carlo method: Hitting and cover times, Undirected s-t Connectivity, expanders and mixing times, probability amplification, approximating #DNF, Markov chain Monte Carlo (3-4 weeks). Pseudorandomness: pseudorandom generators and randomness extractors (1 week). |
| Prerequisites: | CS 357 (Undergraduate Algorithms) or equivalent, basic probability, and graduate standing or consent of instructor. Many students find this course difficult, so a strong math background is highly recommended. In particular, a good knowledge of elementary probability is essential. For example, students should know Chapter 2 and Section 3.2 of Mitzenmacher-Upfal, except possibly for Jensen's Inequality and the analyses of the Coupon Collector problem and Quicksort. We will also spend 2-3 weeks on algebraic techniques. While we will review the necessary theorems about groups and fields, it may be difficult for students who haven't seen this before. |