# Syllabus for CPSC 536N (Randomized Algorithms) 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.

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.

·         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).