CS388R: Randomized Algorithms (Fall 2008)

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).
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
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.

Last modified: September 3, 2008