## CS378 - Randomized Algorithms (Fall 2015)

Logistics: TTh 11:00-12:30
GDC 4.302
Unique Number: 50959
Course web page: http://www.cs.utexas.edu/~diz/378
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Phone: 471-9729
Office: GDC 4.508
Office Hours: TBD.
Text: Mitzenmacher and Upfal, Probability and Computing
Course Overview: Randomness is extremely useful in computer science. Algorithms that make random choices during their execution, known as randomized algorithms, are often faster or simpler than algorithms that don't use randomness. Examples include Quicksort, primality testing, and Monte Carlo simulations. However, such randomized algorithms usually come with a small probability of error, so it is important to bound this error probability. In this undergraduate course, we develop tools and techniques to design and analyze efficient randomized algorithms. This course is theoretical and mathematical; there will be no programming assignments. Each section of the course is built around a method, with example applications to randomized algorithms. We list the topics below.

 Topic Chapter(s) Approximate Time Introduction, Simple Randomized Algorithms 1-2 1-2 weeks Moments and Deviations 3 1 week Tail Inequalities 4 1 week Balls, Bins, and Random Graphs 5 1-2 weeks Probabilistic Method 6 1-2 weeks Markov Chains and Random Walks 7 2 weeks Entropy 9 1 week Monte Carlo Method 10 1-2 weeks Pairwise Independence and Universal Hashing 13 1-2 weeks

Prerequisites: Computer Science 331 or 331H or 357 or 357H. This means that you need the prerequisites and corequisites for CS 331, including Discrete Math (CS 311 or 311H), Probability (SDS 321 or M 362K), and Linear Algebra (SDS 329C, Math 340L, or Math 341).
Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.
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.