Unique Number: 50959
Course web page: http://www.cs.utexas.edu/~diz/378
Office: GDC 4.508
Office Hours: TBD.
|Text:||Mitzenmacher and Upfal, Probability and Computing|
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.
|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.|