The Probabilistic Method

Course Basics

Lecture: Monday, Wednesday, Friday 10:30AM - 11:20AM, Science Center 105
Lab: Wednesday 1:15PM - 2:45PM, Science Center 105
Instructor: Joshua Brody
Email: lastname at cs.swarthmore.edu
Office: Science Center 260
Office Hours: M 3-5, Th 3-4, when my door is open, and by appointment
Textbooks: The Probabilistic Method, by Alon and Spencer.
A Computational Introduction to Number Theory and Algebra, by Victor Shoup.
Discrete Mathematics with Graph Theory, by Goodrich and Parmenter.
Course Discussion: Piazza (mandatory enrollment)

The Alon/Spencer and Shoup books are required, but you only need to purchase the Alon/Spencer book --- the Shoup book is available online for free following the link above.

We will use the Shoup book to develop the basics of probablity theory. Do not be scared by its title. The Shoup book contains lots of material that we won't be using; we will only use Chapter 8 (which is 100% self-contained), and only do introduce/develop probability theory.

The Goodrich/Parmenter book is not required, but if you haven't taken Discrete Mathematics and/or are looking to brush up, it's a good resource.

Welcome to CS49/Math59. In 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. I'll introduce first discrete probability theory, giving you most of what you need to understand randomness in computer science. Most of the course will cover 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.