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 10): Introduction.
Administrative stuff, the stable matching problem, GaleShapley algorithm (Ref: KT, Chapter 1)

Lecture 2 (Aug 19): Divideandconquer.
Binary search, deterministic median finding, Karatsuba for integer multiplication (Ref: KT, Chapter 5; CLRS, Chapter 4 and Section 9.3)

Lecture 3 (Aug 22): Divideandconquer.
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 redblack 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 BellmanFord 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

Lecture 11 (Sep 26) Linear Programming
FordFulkerson Algorithm, Max FlowMin 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

Lecture 15 (Oct 14) Randomized Algorithms
Indicator random variables, the hiring problem, randomized quicksort, randomized contention resolution, tail bounds, Chernoff bound (Ref: CLRS, 5.15.3, 7.37.4; KT, 13.1, 13.9)

Lecture 16 (Oct 17) Hashing

Lecture 17 (Oct 19) NP Hardness
Polynomialtime reductions along with classes P, NP, NPhard, and NPcomplete. Examples of problems in NP. A proof sketch of the CookLevin Theorem. (Ref: KT Chapter 8; DPV Chapter 8)

Lecture 18 (Oct 24) Reductions
Primes is in NP (Pratt's certificate). Examples of polynomialtime reductions and NPcomplete 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 NPhardness. Introduction to Approximation Algorithms. A 1/2approximation algorithm for the Knapsack problem and a (11/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 2approximation for the weighted vertex cover problem. (
Rough Notes)

Lecture 21 (Nov 4) Algorithmic Game Theory

Lecture 22 (Nov 7) Algorithmic Game Theory
Support enumeration for computing Nash equilibrium in twoplayer games. Approximate Nash equilibria and the LiptonMarkakisMehta 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