CPSC 049. The Probabilistic Method

(Cross-listed as MATH 059)
In mathematics and theoretical computer science, we often consider classes of objects (say graphs, circuits or matrices) and we’d like to know if there are objects that have certain nice properties. One way to show these nice objects exist is to look at a random object, and show it has the nice property with nonzero probability. If this is true, there must be some object with this nice property. This is the Probabilistic Method in a nutshell. It has become an essential tool for understanding structure of lots and lots of things in theoretical computer science and combinatorics, even in problems and applications which involve no randomness at all.
This class will start from the ground up, first introducing discrete probability theory, then covering the probabilistic method in detail: how it works, extensions, and most of all lots of applications. We’ll also spend a few weeks discussing NP-Completeness and randomized algorithms.
Group 1 course.
Prerequisite: CPSC 035 and MATH 039, or permission of the instructor.
Natural sciences and engineering.
Lab work required
1 credit.
Catalog chapter: Computer Science
Department website: https://www.swarthmore.edu/computer-science

Access the class schedule to search for sections.