CPSC 536F, WINTER 2016

Handouts

To review Chernoff bound (and other basic concentration inequalities), you can read Nick Harvey's notes.

To review the very basics of probability theory, you may read Chapter 1 of these lecture notes by Matousek and Vondrak. For a slightly more elaborate review (though still without measure theory), you may read this note for a machine learning course at Stanford.
Warning: If the notions in these reviews on probability theory are mostly new to you, you should consider dropping this class, or at least have a discussion with me. Unlike the other sources in this page, these reviews are not supposed to be tutorials.

To learn/review basic probabilistic methods, you may read Chapters 2 and 3 of Matousek and Vondrak's lecture notes.
To get quickly familiar with LP relaxations and integrality gap, you may read Sections 10.1 and 10.2 of these lecture notes by Shuchi Chawla. Section 10.2 and 10.3 give you a good idea how rounding algorithms could work to give approximations.
Optional: Michel Goemans's lecture notes on the ellipsoid method.

Problem Sets