Lecture 1 (Aug 10): Introduction.

Administrative stuff, the stable matching problem, Gale-Shapley algorithm (Ref: KT, Chapter 1)

Lecture 2 (Aug 19): Divide-and-conquer.

Binary search, deterministic median finding, Karatsuba for integer multiplication (Ref: KT, Chapter 5; CLRS, Chapter 4 and Section 9.3)

Lecture 3 (Aug 22): Divide-and-conquer.

Polynomial multiplication via FFT, AA trees as an example of balanced BST's (Ref: KT, Section 5.6; CLRS, Chapter 30; for balanced BST's, see CLRS, Chapter 13 for red-black trees and this webpage for AA trees)

Lecture 4 (Aug 29): Greedy algorithms.

Unweighted interval scheduling, scheduling to minimize lateness (Ref: KT, Sections 4.1 and 4.2)

Lecture 5 (Aug 31): Greedy Algorithms.

Dijkstra's algorithm, minimum spanning trees (Ref: KT, Sections 4.4 and 4.5)

Lecture 6 (Aug 31): Dynamic Programming.

Weighted interval scheduling

Lecture 7 (Sep 7): Dynamic Programming.

Longest Common Subsequence and the Bellman-Ford Algorithm (Ref: CLRS, Section 15.4; KT, Section 6.8)

Lecture 8 (Sep 12): Amortized analysis.

Aggregate analysis, accounting method and potential function method for analyzing multiple pops on a stack and dynamic tables (Ref: CLRS, Chapter 17, Lecture notes by Jeff Erickson)

Lecture 9 (Sep 19) Linear Programming

Introduction to Linear Programming, examples, and the Simplex Method (Rough Notes)

Lecture 10 (Sep 21) Linear Programming

LP applications and Maximum Flow (Rough Notes)

Lecture 11 (Sep 26) Linear Programming

Ford-Fulkerson Algorithm, Max Flow-Min Cut Theorem and Applications of Max Flow (Rough Notes)

Lecture 12 (Sep 28) Linear Programming

LP Duality and Min Cost Perfect Matching in Bipartite Graphs (Rough Notes)

Lecture 13 (Oct 3) Randomized Algorithms

Introduction and Recursive Majority

Lecture 14 (Oct 5) Randomized Algorithms

Skip lists (Ref: Lecture notes by Jeff Erickson)

Lecture 15 (Oct 14) Randomized Algorithms

Indicator random variables, the hiring problem, randomized quicksort, randomized contention resolution, tail bounds, Chernoff bound (Ref: CLRS, 5.1-5.3, 7.3-7.4; KT, 13.1, 13.9)

Lecture 16 (Oct 17) Hashing

Lecture 17 (Oct 19) NP Hardness

Polynomial-time reductions along with classes P, NP, NP-hard, and NP-complete. Examples of problems in NP. A proof sketch of the Cook-Levin Theorem. (Ref: KT Chapter 8; DPV Chapter 8)

Lecture 18 (Oct 24) Reductions

Primes is in NP (Pratt's certificate). Examples of polynomial-time reductions and NP-complete problems: Circuit SAT reduces to SAT, which in turn reduces to 3SAT. Also, 3SAT reduces to Independent Set. (Ref: Notes on Pratt's certificate; DPV Chapter 8)

Lecture 19 (Oct 26) Approximation Algorithms

Coping with NP-hardness. Introduction to Approximation Algorithms. A 1/2-approximation algorithm for the Knapsack problem and a (1-1/e)-approximation algorithm for the Maximum Coverage problem. (Rough Notes)

Lecture 20 (Nov 2) Approximation Algorithms

A (ln n)-approximation algorithm for the General Set Cover problem. LP rounding to obtain a 2-approximation for the weighted vertex cover problem. (Rough Notes)

Lecture 21 (Nov 4) Algorithmic Game Theory

Introduction to Algorithmic Game Theory. Two-Player Zero-Sum Games and Linear Programming. (Notes by Costis Daskalakis)

Lecture 22 (Nov 7) Algorithmic Game Theory

Support enumeration for computing Nash equilibrium in two-player games. Approximate Nash equilibria and the Lipton-Markakis-Mehta algorithm. (Rough Notes)

Lecture 23 (Nov 14) Streaming Algorithms I

The streaming model, the distinct elements problem. (some notes)

Lecture 24 (Nov 16) Exact Algorithms II

Finishing analysis of the distinct elements problem, the AMS Sketch (Lecture 6 of these notes)