Max-SAT and its approximation: an application of first moment method -- Read Section 1.1 in (B8); or (W4); or Section 13.4 in (B1)

Conditional probability and graph min-cut -- Read the subsection on global mincut in (B1); or (B2)

Lower bound on crossing number: a proof using elementary probability -- Read from graph theory part of (B9)

Use of concentration inequalities Markov and Chebyshev with applications to hashing -- Read "Five essential tools for the Analysis of Randomized Algorithms" from (W4)'s "a Second Course in Algorithms"

Chernoff and union bound -- Load balancing Read Section 13.10 on Load Balancing in (B1)

Packet Routing -- Read Section 13.11 on Packet Routing in (B1)

Probabilistic Methods:
Balancing vectors, Ramsey Numbers, Cuts in graphs, Independent sets via alteration and random permutation --
Read relevant subsections from Chapters 1, 2 and 3 of (B6)

Probabilistic Methods:
Random permutations, Erdős-Ko-Rado Theorem, (k,l)-systems, dominating set, combinatorial geometry --
Read relevant subsections from Chapters 1, 2 and 3 of (B6)

Chernoff and union bound:
Packet routing --
Read relevant subsections from Chapter 13.11 of (B1) and handout supplied in the class

Lovasz Local Lemma:
Read from (B2), (B6) or (W5)

Understanding Lovasz Local Lemma and its applications: Read from (B2), (B6) or (W5)

Constructive Lovasz Local Lemma: Read from "Miscellaneous Lecture Notes" of (W4)

Random walk on Z and Z²: Read Chapter 14 from (W1)

Random Walk on a line graph and 2SAT:
Read relevant sections from Markov Chains and Random Walks chapter from (B2)

Chapman-Kolmogrov Equations;
Communicating states and communicating classes, irreducible Markov Chains;
Existence and Uniqueness of Stationary Distribution:
Read relevant portions from Chapter 1 of (B10) and Chapter 1 of (W7)

Periods in MC;
Total variation distance and its properties;
Statement of Convergence Theorem and its consequences:
Read from Sections 1.3, 4.1 and 4.3 and the proof of Lemma 1.27 from Chapter 1 of (B10)

Proof of Convergence Theorem;
Classification of states: Recurrent, transient and positive recurrent;
Brief overview of spectral technique:
Read from Sections 1.5.2, 4.3, and 21.1 of (B10) and Chapter 5 of (W7)

Random Graph -- G(n,p) and G(n,N) models
Degree distribution in G(n,p)
Existence of triangles in G(n,p)
Read from the Chapter on Random Graphs in (W3) and can consult (B2) and (B6)

Phase transition: first and second moment method;
Disappearance of isolated vertices;
Threshold for graph connectivity
Read from the Chapter on Random Graphs in (W3) and can consult (B2) and (B6)

Phase transition (contd.): Emergence of cycles
Phase transitions for monotone properties;
Read from the Chapter on Random Graphs in (W3) and can consult (B2) and (B6)

Randomized algorithm for closest pair of points using universal hashing
Read from the Chapter on Randomized Algorithms (sections on universal hashing and closest pair) in (B1); also consult (W1)

Randomized Incremental Construction and backward analysis:
Sorting (again) and convex hull
Read from relevant portions of Chapter 1 in (B5); also consult Chapters 9.1 and 9.2 in (B3)

Randomized Incremental Construction and backward analysis:
Trapezoidal decomposition
Read from the relevant chapters in (W2); for the Chernoff bound, see (B4)

Set systems, primal and dual set systems;
Clarkson-Shor technique and counting for set systems
Read from class notes and
M. Sharir: The Clarkson-Shor Technique Revisited and Extended. Combinatorics, Probability & Computing 12(2): 191-201, 2003.

VC dimension and shallow cell complexity:
Projection, shattering, VC dimension;
Radon's theorem and its use in finding VC dimension;
Sauer-Shelah lemma Read from Chapter 5 in (B5); also consult (B11) and (B12);
For web resource, consult E. Welzl's notes and V. Koltun's notes;

VC dimension and epsilon-nets
Read from Chapter 5 in (B5); also consult (B11) and (B12);
For web resource, consult E. Welzl's notes and V. Koltun's notes;

VC dimension and epsilon-nets
Read from Chapter 5 in (B5); also consult (B11) and (B12);
For web resource, consult E. Welzl's notes and V. Koltun's notes;

Randomized incremental construction for LP in low dimensions
Read from (W2); also can consult (B3)

Randomized algorithm for LP (by Clarkson)
Read from (B3)

Randomized lower bounds, Yao's minimax principle
Read from Amit Chakrabarti's notes and also consult (B3)

Randomized lower bounds for game tree evaluation and sorting: application of Yao's minimax principle
Read from Amit Chakrabarti's notes for randomized sorting lower bound and (B3) for game tree evaluation

Randomized complexity classes
Read from (B3) and can consult (B13)

Martingales
Read from (B2) and (W1); also can consult (B3) and (B14)

Martingales: Azuma Hoeffding inequalities
Read from (B2) and (W1); also can consult (B3) and (B14)

Martingales, Lipschitz condition and Azuma Hoeffding inequalities; applications
Read from (B2) and (W1); also can consult (B3) and (B14)

Derandomization using conditional expectation: application using MAX-CUT
Read from (B2)