Lecture 1 (Aug 6): Randomized algorithm for 2SAT, Schoening's algorithm

Lecture 2 (Aug 9): Schoening's algorithm (contd.), Approximation algorithms for MAX-SAT

Lecture 3 (Aug 11): Randomized Rounding

Lecture 4 (Aug 20): Online Paging, The Marker algorithm

Lecture 5 (Aug 22): Randomized online paging (contd.)

Lecture 6 (Aug 27): The minimax principle

Lecture 7 (Sep 3): Set Cover

Lecture 8 (Sep 5): LP-duality

Lecture 9 (Sep 10): LP-duality (contd.)

Lecture 10 (Sep 12): LP-duality (contd.)

Lecture 11 (Sep 17): Dimensionality Reduction: Lecture by Amit Deshpande - slides

Lecture 12 (Sep 19): Metric Embedding: Lecture by Amit Deshpande - slides

Lecture 13 (Sep 22): Set Multicover

Lecture 14 (Sep 24): Primal-dual schema for set cover, multicut in trees

Lecture 15 (Sep 26): Primal-dual schema for multicut in trees (contd.)

Lecture 16 (Oct 8): Multiway Cut

Lecture 17 (Oct 10): Multiway Cut (contd.)

Oct 13: Mid-Term Exam

Lecture 18 (Oct 15): Max-Cut

Lecture 19 (Oct 22): SDP for max-cut (contd.)

Lecture 20 (Oct 24): Primality Testing: Miller-Rabin algorithm

Lecture 21 (Oct 25): Primality Testing: AKS algorithm Notes on this algorithm (by Jaikumar Radhakrishnan in 2002)

Lecture 22 (Oct 29): Primality Testing: AKS algorithm (contd.)

Lecture 23 (Nov 5): Primality Testing: AKS algorithm (contd.)

Lecture 24 (Nov 7): Parallel Maximal Independent Set

Lecture 25 (Nov 12): Sorting on a PRAM

Lecture 26 (Nov 14): Sorting on a PRAM (contd.)

Nov 19: Discussion

Nov 21: Discussion

Lecture 27 (Nov 26): Graph Sparsification while maintaining cuts: Lecture by Ramesh Hariharan - slides

Lecture 28 (Nov 28): Graph Sparsification while maintaining cuts (contd.)