| 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: TTh 2-3, or by appointment. |
| TA: | Raghu Meka
Email: raghu@cs.utexas.edu Office: TAY 3.108 Phone: 471-9520 Office Hours: M 3-4. |
| Texts: | Required:
R. Motwani and P. Raghavan,
"Randomized Algorithms"
(
errata).
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 list of topics follows.
Introduction: Quicksort, Min Cut, RP and BPP (1 week). Probabilistic tools and techniques: Moments, tail inequalities, pairwise independence, randomized routing, occupancy problems, martingales, probabilistic method, random projection (4-5 weeks). Algebraic techniques and isolation: Fingerprinting, polynomials, matching and isolation lemma, primality testing (2-3 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. |
| Grading: |
30%: Homework (6-8 problem sets) 25%: Midterm 45%: Final exam |
| Exams: | The midterm will be held in class on Tuesday, October 28. The final exam will be cumulative and held on Friday, December 12, from 9am - noon. No make-up exams will be given, so please plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper, with writing on both sides; for the final you may bring two such sheets. No calculators are allowed (they won't be necessary). |
| Homework policy: |
Collaboration policy: I encourage you to discuss homework
problems with your classmates.
However, you must write up your own solutions.
Furthermore, you must acknowledge any collaboration by writing the
names of your collaborators on the front page of the assignment.
Citation policy: If you use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. Submission policy: Homeworks are due at the beginning of class. Submit late homeworks directly to the TA. Late policy: Each student has three late days that they can use during the semester with no penalty (one assignment three days late, or one assignment two days late and one assignment one day late, etc.). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours (so it begins and ends at 11:00am). The weekend doesn't count, so Friday 11am to Monday 11am counts as one day. I may not allow late days for certain assignments. |
|
Students with Disabilites: |
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations. |