Date  Topic 
Dec 23 
Back to Linear Programming: relaxations, primaldual algorithms, and approximations of NPhard problems.
Introduction to vector and semidefinite programs. The GoemansWilliamson algorithm.
What was this course about and what's next?

Dec 16 
Perfect matchings through polynomial identity testing: randomized parallel algorithms.
Overview of the hardness of the determinant and permament, primality testing and PIT.
Back to approximation algorithms: greedy approximations and primaldual algorithms.

Dec 9 
More on randomized algorithms: error reduction, dealing with dependencies,
polynomial identity testing

Dec 2 
All pairs shortest paths (APSP) in small parallel time.
Divide and Conquer: Fast Integer Multiplication, Strassen's Matrix Multiplication algorithm, sublinear DnC time algorithms
Time lower bounds (for all algorithms) in the query model.

Nov 25 
Dynamic Programming (many examples),
dynamic programming and space requirements, trading space for time 
Nov 11 
The complete LP duality theorem and its proof
The Simplex Algorithm
Linear relaxations of Integer programs and approximations of Set Cover.

Nov 4 
Linear Programming Duality: a geometric (selfcontained) proof of Farkas Lemma and LP Duality. 
Oct 28 
Introduction to the Geometry of Linear programs.
Why Linear Programs can be computed (and in particular in exponential time)?
Extreme points, Corners, Basic Feasible Solutions, and all that.

Oct 21 
Introduction to Linear programming.
Guest lecture by Peter Bro Miltersen on Stochastic Games.

Oct 14 
More on beautiful duality:
polytime and strong polytime, EdmondsKarp. Reductions and
Bipartite Matching.

Sep 30 
Beautiful duality: Maxflow, Mincut, duality arguments,
FordFulkerson.

Sep 23 
Greedy algorithms: interval scheduling, correctness of interval scheduling.
Overview of basic graphs algorithms,
encoding graphs and datastructures (this completely covers chapters 14 from the text) 
Sep 16 
What is it about?
The stable marriage problem: the importance of proofs of correctness 