Lecture 1: Deterministic Linear-time Median computation Lecture 2: Median computation continued; Divide and conquer for closest pair problem Lecture 3: Analysis for closest pair algorithm; Divide and conquer for polynomial multiplication Lecture 4: The Fast Fourier Transform for polynomial multiplication Lecture 5: The Fast Fourier Transform continued. Lecture 6: Randomization: contention resolution. Defining probability spaces and events. Lecture 7: Global min-cut using edge contraction; conditional probabilities and independence Lecture 8: Global min-cut continued. Lecture 9: Random variables, linearity of expectation. Universal hashing Lecture 10: Universal hashing continued. Marking algorithm for caching. Lecture 11: Analysis of deterministic and randomized marking algorithms. Lecture 12: Dynamic programming - Longest common subsequences Lecture 13: LCS continued. Greedy Algorithms: Activity Selection Lecture 14: Midterm Lecture 15: Greedy algorithm continued, dynamic programming for weighted activity selection Lecture 16: weighted activity selection continued. The max-flow problem. Lecture 17: Residual networks and the Ford-Fulkerson algorithm Lecture 18: Min-cuts, proof of correctness of FF algorithm, variants of the algorithm with better guarantees on no. of iterations Lecture 19: Applications of Max-Flow: Image segmentation and maximum matching Lecture 20: The image segmentation application continued. Review of dynamic programming Lecture 21: The issue of word size. Poly-time reducibility. Lecture 22: Examples of poly-time reductions -- Independent set to vertex cover and back, 3SAT to independent set. Lecture 23: Efficient verifiers and a definition of NP. Examples. Lecture 24: More examples of problems in NP. NP-completeness and its significance. A first NP-complete problem - Circuit-SAT. Lecture 25: Np-completeness of 3SAT via reduction from circuit-sat. NP-completeness of independent set and vertex cover. Poly-time reduction of 3SAT to 3-coloring. Lecture 26: Approximation algorithms for vertex cover and set cover. Lecture 27: Approximation algorithm for the k-center problem. Lecture 28: The k-center problem continued.