CS378 - Randomized Algorithms (Spring 2018)

Syllabus: syllabus in pdf
syllabus in html
Logistics: MW 2-3:30
GDC 5.302
Unique Number: 51695
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: MW 3:30-4:30
TA: Fu Li
Email: fuli.theory.research@gmail.com
Office Hours: TTh 4-5, GDC 1.302, Desk 1
Text: Mitzenmacher and Upfal, Probability and Computing, 2nd edition
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 Bounds 4 1 week
Balls, Bins, and Random Graphs 5 1 week
Probabilistic Method 6 1 week
Markov Chains and Random Walks 7 1-2 weeks
Entropy 10 1 week
Monte Carlo Method 11 1-2 weeks
Pairwise Independence and Universal Hashing 15 1-2 weeks

Useful Pointers: My 100-second talk on randomness on The Academic Minute.
My essay Can Random Coin Flips Speed Up a Computer?
Review sheet for some basic concepts.
My lecture notes on random graphs.
My lecture notes on coding theory.
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: April 4, 2018