Homepage of Kavitha Telikepalli Details of lectures
Lecture Notes (contributed by all the students)
Lecture 1 (Aug 6): Randomized algorithm for 2SAT, Schoening's algorithm (notes by Diptendu/Priyank)
Lecture 2 (Aug 9): Schoening's algorithm (contd.), Approximation algorithms for MAX-SAT
Lecture 3 (Aug 11): Randomized Rounding (notes by Devansh/Sourjya)
Lecture 4 (Aug 20): Online Paging, The Marker algorithm (notes by Janardhan/Satadru)
Lecture 5 (Aug 22): Randomized online paging (contd.)
Lecture 6 (Aug 27): The minimax principle (notes by Hari Prasad/Pooja)
Lecture 7 (Sep 3): Set Cover
Lecture 8 (Sep 5): LP-duality (notes by Arun/Dilip)
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 (notes by Mayur/Urvang)
Lecture 14 (Sep 24): Primal-dual schema for set cover, multicut in trees (notes by Abhijeet/Sunil)
Lecture 15 (Sep 26): Primal-dual schema for multicut in trees (contd.)
Lecture 16 (Oct 8): Multiway Cut (notes by Abhirama/Chaitanya)
Lecture 17 (Oct 10): Multiway Cut (contd.)
Oct 13: Mid-Term Exam
Lecture 18 (Oct 15): Max-Cut (notes by Ravi/Srikanth)
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 (notes by Raghav)
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.)