CPSC 091T. Special Topics: Randomized Algorithms

In the past 40 years, randomization has proved to be a key tool in the design and analysis of algorithms. Randomized algorithms can be simpler and/or more efficient than deterministic algorithms. It can also better capture several computational problems that arise in nature.

This course provides an introduction to algorithm design with a focus on randomized algorithms and data structures. Topics include analysis of algorithms, basics of discrete probability including tail inequalities, the probabilistic method, NP-Completeness, and applications to graph algorithms, streaming algorithms, communication complexity, and machine learning.
This is a Group 1 course.
Prerequisite: CPSC035 is required. Mathematics background at the level of Linear Algebra or higher is required but may be taken concurrently.

No prior knowledge of probability is necessary.
Natural science.
1.0 credit
Spring 2023. Brody.

Access the class schedule to search for sections.

Close Window