Randomized Algorithms
High school summer course, MIT High School Studies Program, 2023
Randomized algorithms are algorithms that have access to a random source during computation, meaning that the output of the algorithm is non-deterministic. Oftentimes, randomized algorithms are useful in reducing computation time needed for otherwise slow or complex tasks. How do we design randomized algorithms to speed up computation without trading off correctness of our output? In this course, we will cover several Las Vegas and Monte Carlo algorithms, such as randomized quicksort, Frievald’s algorithm, game tree evaluation, and primality testing algorithms.