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.
<![if !supportLists]>· <![endif]>This offering: http://www.cs.ubc.ca/~nickhar/W15
<![if !supportLists]>· <![endif]>Previous offering: http://www.cs.ubc.ca/~nickhar/W12, with lecture notes
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.
<![if !supportLists]>· <![endif]>Recommended textbook:
<![if !supportLists]>o <![endif]>M. Mitzenmacher and E. Upfal. “Probability and Computing”
<![if !supportLists]>§ <![endif]>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.
<![if !supportLists]>· <![endif]>Optional textbooks:
<![if !supportLists]>o <![endif]>R. Motwani and P. Raghavan. “Randomized Algorithms”
<![if !supportLists]>§ <![endif]>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.
<![if !supportLists]>o <![endif]>D. Dubhashi and A. Panconesi. “Concentration of Measure for the Analysis of Randomized Algorithms”
<![if !supportLists]>§ <![endif]>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.
<![if !supportLists]>o <![endif]>N. Alon and J. Spencer. “The Probabilistic Method”
<![if !supportLists]>§ <![endif]>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.
<![if !supportLists]>· <![endif]>70%: Assignments (around six)
<![if !supportLists]>· <![endif]>5%: Project proposal
<![if !supportLists]>· <![endif]>25%: Project
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).