Introduction to the course;

Polynomial reductions and NP-Complete problems -- Read the subsection on NP-Complete problems in (B1);

Introduction to approximation algorithms and a 2-factor approximation algorithm for vertex cover -- Read from (B15) and (B16)

A 2- and 3/2-factor approximation for metric TSP;
Inapproximability result for TSP -- Read from (B15)

An FPTAS for Knapsack -- Read from (B15)

Introduction to LP and a deterministic LP rounding for a f-factor approximation of Set Cover -- Read from (B16)

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)

Randomized quicksort -- Read from (B2)

Concentration inequalities: Markov and Chebyshev -- Read "Five essential tools for the Analysis of Randomized Algorithms" from (W4)'s "a Second Course in Algorithms"; and Chapter 3 in (B2)

Chernoff bounds Read Chapter 4 in (B2)

Chernoff bounds (contd.) Read "Five essential tools for the Analysis of Randomized Algorithms" from (W4)'s "a Second Course in Algorithms"; and Chapter 4 in (B2)

Chernoff bounds applied to Balls and bins; load balancing -- Read (B1) and Chapter 4 in (B2)

Packet routing -- high probability bounds using Chernoff bounds Read from (B2)

Quicksort -- high probability bounds using Chernoff bounds Read from handout given in the class

Randomized incremental construction and backward analysis in computational geometry: LP in fixed dimensions and minimum enclosing disk ---
Read from relevant chapters of (B4) and (W2)

Probabilistic Methods: Ramsey Numbers, Erdős-Ko-Rado Theorem, Hamiltonian paths,
Sample and modify: independent set and graphs with high girth and high chromatic number --
Read relevant subsections from Chapters 2, 3 and 4 of (W8)

Trapezoidal decomposition and point location
Read from (W2) and Chapter 6 of (B4)

Trapezoidal decomposition and point location (contd.):
Read from (W2) and Chapter 6 of (B4)

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

Lovasz Local Lemma and its applications: edge disjoint paths, list coloring, asymmetric LLL Read from (B2), (B6) or (W5)

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

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

Random graphs: degree distribution, existence of triangles, phase transition, isolated vertices.
Read from relevant section of (W3)

Martingales, Doob Martingales, Stopping Times, Wald's equation
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)

General form of Azuma Hoeffding inequalities; more applications
Read from (B2) and (W1); also can consult (B3) and (B14)

Range spaces and VC dimension:
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 (B7) and (W2) and class notes;
For web resource, consult E. Welzl's notes and V. Koltun's notes;

LP duality: Weak and strong duality, complementary slackness
Read from (B15) and (B16)

VC dimension and epsilon-nets: epsilon-net theorem
Set cover and Hitting set of range spaces with bounded VC dimension vis iterative reweighting
Read from Chapter 5 in (B5); also consult (B7) and (W2);
For web resource, consult E. Welzl's notes and V. Koltun's notes;

Role of LP duality in approximation -- Set cover; Feedback Vertex Set
Read from (B16) and (B15);

Randomized rounding for approximation
Read from (B16) and (B15);

k-centre problem: inapproximability result using dominating set
MAX-CUT and MAX-SAT Read from (B16) and (B15)

Derandomization using conditional expectation
Read from (B16)

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