| Date     || Topic |
| Dec 23
|| Back to Linear Programming: relaxations, primal-dual algorithms, and approximations of NP-hard problems.
Introduction to vector and semi-definite programs. The Goemans-Williamson 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 primal-dual 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 (self-contained) 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:
poly-time and strong poly-time, Edmonds-Karp. Reductions and
| Sep 30
|| Beautiful duality: Max-flow, Min-cut, duality arguments,
| Sep 23
|| Greedy algorithms: interval scheduling, correctness of interval scheduling.
Overview of basic graphs algorithms,
encoding graphs and data-structures (this completely covers chapters 1-4 from the text)
| Sep 16
|| What is it about?
The stable marriage problem: the importance of proofs of correctness