After (or sometimes before) lectures, we will write a blurb on what we did and provide references
to where the material is from. Sometimes we may provide pdfs of rough notes.
-
Lecture 1 (Aug 8): Introduction.
Administrative stuff, the stable matching problem, Gale-Shapley algorithm (Ref: KT, Chapter 1)
-
Lecture 2 (Aug 13): Stable Matching.
The stable matching problem (continued)
-
Lecture 3 (Aug 20): Divide and Conquer
Integer Multiplication (Karatsuba’s Algorithm) and Strassen’s Matrix Multiplication (Ref: DPV, Chapter 2)
-
Lecture 4 (Aug 27): Divide and Conquer
Fast Fourier Transform (Ref: DPV, Chapter 2)
-
Lecture 5 (Aug 29): Divide and Conquer
Closest Pair Problem (Ref: CLRS, Section 33.4)
-
Lecture 6 (Sept 3): Dynamic Programming
Weighted Interval Scheduling and Longest Common Subsequence
-
Lecture 7 (Sept 5): Dynamic Programming
Bellman-Ford Algorithm and Chain Matrix Multiplication
-
Lecture 8 (Sept 10): Max Flow-Min Cut
Ford-Fulkerson Algorithm
-
Lecture 9 (Sept 12): Max Flow-Min Cut
Ford-Fulkerson Algorithm (continued)
-
Lecture 10 (Sept 17): Max Flow-Min Cut: Applications
Perfect Matching and Edge-disjoint paths
-
In-Class Test (Sept 19)
Covering Lectures 1 through 7
-
Lecture 11 (Sept 24): NP-hardness
Complexity classes P and NP. Cook-Levin Theorem (proof sketch). Examples of NP-complete problems.
-
Lecture 12 (Sept 26): NP-hardness
Primes is in NP (Pratt's certificate). Reductions: Circuit SAT to SAT, and then to 3SAT. Also, 3SAT to independent set
-
Lecture 13 (Oct 1): Greedy Algorithms
Minimum Weight Spanning Tree: Boruvka's Algorithm
-
Lecture 14 (Oct 3): Greedy Algorithms
Matroids and Finding Maximum Weight Bases
-
Lecture 15 (Oct 10): Linear Programming
Introduction (Ref: DPV, Chapter 7)
-
Lecture 16 (Oct 15): Linear Programming
Simplex Method
-
Lecture 17 (Oct 17): Linear Programming
Duality
-
Lecture 18 (Oct 22): Linear Programming
Applications: Finding Minimum Weight Matchings in Bipartite Graphs (Hungarian Algorithm)
-
Class Test (Oct 29)
-
Lecture 19 (Nov 5) Coping with Computational Hardness
2-Approximation Algorithm for the Knapsack Problem
-
Lecture 20 (Nov 12) Approximation Algorithms
(1-1/e)-Approximation Algorithm for Maximum Coverage and (ln n)-Approximation Algorithm for Set Cover
-
Lecture 21 (Nov 14) Approximation Algorithms
(ln n)-Approximation Algorithm for Weighted Set Cover and LP rounding for Vertex Cover
-
Lecture 22 (Nov 19) Randomized Algorithms
Approximate Median and Karger's Min-Cut Algorithm