CS378 - Randomized Algorithms (Fall 2015)

Syllabus: syllabus in pdf
syllabus in html
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: M 2-3, W 1-2.
TA: Xue Chen
Email: xchen@cs.utexas.edu
Office Hours: Tu 10-11, F 1-2, TA Station of GDC.
Who should take this? Students who like theory, probability, and algorithms. This course is excellent preparation for graduate school.
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.
Useful Pointers: My essay Can Random Coin Flips Speed Up a Computer?
Theory of Computing Blog Aggregator
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: August 28, 2015.