2011-12 Term 2

**Description**

Over the past few decades, probabilistic techniques
have become pervasive in most areas of theoretical computer science and many areas
of discrete mathematics. These techniques have also been increasingly used in
more applied areas, such as computer networking, scientific computing and
databases. This course will give an introduction to these techniques and
showcase some of the astonishing algorithms that have been developed. I will
cover both classical topics of fundamental importance and topics that are
relevant to current research.

**Webpage: **http://www.cs.ubc.ca/~nickhar/W12

**Lecture Notes Blog: **http://nickhar.wordpress.com/

**Resources**

There is no required text for this class, although
the following four books are worth owning. (They are listed in decreasing order
of relevance to this class.) I regularly
use all of these books in my own research.

·
**Recommended
textbook:**

o M. Mitzenmacher and E. Upfal. “Probability and Computing”

§
This book can be viewed as
an updated, gentler version of Motwani-Raghavan. It
is easier to read, less encyclopedic, and adds several important modern topics.
Many great exercises and mostly error-free.

·
**Optional textbooks:**

o R. Motwani and P. Raghavan. “Randomized Algorithms”

§
This is the classic book on
the subject. It covers quite a lot of topics, but it is now over 15 years and
so it misses some modern developments. Everything in here is worth knowing,
although there are a few typos.

o D. Dubhashi and A. Panconesi. “Concentration of Measure for the Analysis of
Randomized Algorithms”

§
This book covers various
“concentration inequalities”, which are one of the important tools used in
randomized algorithms (but certainly not the only tools). It was written very
recently, so it covers some topics that are not found in other books. It is
quite readable, although there are a few typos.

o N. Alon and J. Spencer.
“The Probabilistic Method”

§
This is really a book on
discrete mathematics, but it occasionally touches on theoretical computer
science. However, it covers a large number of techniques, almost all of which
were eventually used in computer science too. The book is quite terse and
requires concerted effort to read.

**Grading Scheme**

·
40%: Assignments (three or four)

·
10%: Project proposal

·
50%: Project

**Prerequisites**

**The
most important prerequisite for this course is a thorough understanding of
discrete probability theory. **I
expect you to understand the following concepts:

- Sample
spaces, events
- Random
variables, independence
- Law
of total probability

- Expectation,
linearity of expectation
- Conditional
probabilities and conditional expectations
- Common
distributions: Bernoulli, Binomial, Geometric
- Markov’s
Inequality

To review these topics, I recommend
looking at Mitzenmacher & Upfal
Sections 1.2, 2.1-2.4 or Lehman, Leighton
and Meyer Ch 14-18.

I would also expect that the students have a strong
background in algorithms (e.g., CPSC 420), and a decent background in some of complexity
theory (e.g., CPSC 421), optimization (e.g., MATH 340, CPSC 546), graph theory
(e.g., MATH 443) and combinatorial optimization (e.g., MATH 523).