syllabus in pdf
syllabus in html
Unique Number: 51695
Course web page: http://www.cs.utexas.edu/~diz/378
Office: GDC 4.508
Office Hours: MW 3:30-4:30
Office Hours: TTh 4-5, GDC 1.302, Desk 1
|Text:||Mitzenmacher and Upfal, Probability and Computing, 2nd edition|
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
Each section of the course is built around a method, with example
applications to randomized algorithms.
We list the topics below.
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.