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:
·
This
offering: http://www.cs.ubc.ca/~nickhar/W15
·
Previous
offering: http://www.cs.ubc.ca/~nickhar/W12,
with lecture notes
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. It has many great
exercises which are helpful for learning the material.
·
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. Every theoretical computer scientist
ought to know everything in here.
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 quite
recently, so it covers some topics that are not found in other books.
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
·
70%: Assignments (around six)
·
5%: Project proposal
·
25%: 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:
This material should be covered by
the introductory probability courses like MATH 302
or STAT 302. 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. It may
be helpful to have taken an advanced probability course like MATH 418 or STAT 547C.
It
is desirable to have a solid background in algorithm design (ideally CPSC 420
or CPSC 500) and linear
algebra (ideally MATH 310).
It may be helpful to have some familiarity with complexity theory (e.g., CPSC 421/501), optimization (e.g., MATH 340, MATH 523, CPSC
546) and combinatorics (e.g., MATH 443, MATH 503).