Description
Over the past few decades, probabilistic techniques
have become pervasive in most areas of theoretical computer science and many
areas of discrete mathematics. This course aims to give an introduction to
these techniques, and to showcase some of the interesting results that can be
proven using these techniques. The emphasis is on applications in theoretical
computer science rather than in discrete mathematics.
Resources
·
Recommended
textbook:
M. Mitzenmacher and
E. Upfal. “Probability and Computing”
·
Other relevant textbooks:
R. Motwani and P. Raghavan. “Randomized Algorithms”
D. Dubhashi
and A. Panconesi. “Concentration of Measure for the
Analysis of Randomized Algorithms”
N. Alon
and J. Spencer. “The Probabilistic Method”
Grading Scheme
A combination of assignments (about 3) plus a course 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:
To review these topics, see Mitzenmacher & Upfal Sections
1.2, 2.1-2.4 or Lehman,
Leighton and Meyer Ch 14-18.
Ideally, I would also expect that the students have a
decent background in algorithms (e.g., CS 466), complexity theory (e.g., CS
365), optimization (e.g., CO 355/602), and combinatorial optimization (e.g., CO
450).
Note for students with disabilities
The Office for Persons with Disabilities (OPD),
located in Needles Hall, Room 1132, collaborates with all academic departments
to arrange appropriate accommodations for students with disabilities without
compromising the academic integrity of the curriculum. If you require academic accommodations to
lessen the impact of your disability, please register with the OPD at the
beginning of each academic term.