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