| Logistics: |
TTh 11-12:30
GDC 5.302 Unique Number: 55195 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: TBD |
|||||||||||||||||||||||||||
| Who should take this? | Students interested in theory, probability, and algorithms, and who like a challenge. This course is excellent preparation for graduate school. | |||||||||||||||||||||||||||
| Text: |
Mitzenmacher and Upfal,
Probability and Computing, 2nd edition
Errata |
|||||||||||||||||||||||||||
| 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.
This course should be similar to the 2024 version.
We list the topics below.
|
|||||||||||||||||||||||||||
| Prerequisites: | Computer Science 331 or 331H. 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). Strong intuition about probability is essential; I recommend taking this class only if you received an A in Probability. Here is some mathematical background that we will use. | |||||||||||||||||||||||||||
| Useful Pointers: |
My
100-second talk on randomness on The Academic Minute.
My essay Can Random Coin Flips Speed Up a Computer? |
|||||||||||||||||||||||||||
| Laptops/Phones: | The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you use them only for class-related purposes. All phones must be silenced. | |||||||||||||||||||||||||||
| Canvas: | We will use Canvas, which contains Ed Discussion. Homeworks and grades will be posted on Canvas. We will use Ed Discussion for class discussion. Instead of emailing questions to the teaching staff, please post your questions to Ed Discussion. | |||||||||||||||||||||||||||
|
Students with Disabilites: |
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. |