| Logistics: | TTh 11-12:30 TAY 3.144 Unique Number: 56645 Course web page: http://www.cs.utexas.edu/~diz/395T |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: TAY 3.134 Phone: 471-9729 Office Hours: W 2-3 and F 3-4, or by appointment. |
| TA: | Anup Rao
Email: arao@cs.utexas.edu Office (for office hours): ESB 229 Office (for all other purposes): TAY 3.108 Phone: 471-9520 Office Hours: M 3-4 |
| 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 50-60% 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.
A tentative list of topics follows.
Introduction and Algebraic techniques : Fingerprinting, polynomials, RP and BPP, primality testing (2-3 weeks). Probabilistic tools and techniques: Min Cut, moments, tail inequalities, pairwise independence, randomized routing, occupancy problems, martingales, probabilistic method, isolation lemma and matching, random projection (5-6 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 mathematical and computational sophistication. |
| Grading: |
25%: Homework (6-8 problem sets) 30%: Midterm 45%: Final exam |
| Exams: | The midterm will be held in class on October 24. The final exam will be cumulative and held on Thursday, December 14, from 2-5pm. 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. Late homeworks should be submitted directly to the TA. Late policy: Each student has two late days that they can use during the semester with no penalty (one assignment two days late or two assignments one day late). 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). |
|
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. |