Date | Topic |

Jun 8 |
Putting everything together: review class |

Jun 1 |
The second streaming approximation algorithm for F_0: tradeoffs between quality of approximation and space |

May 31 |
The proof for the bounds on the first distinct elements approximation algorithm |

May 25 |
Introduction streaming lower bounds via Communication Complexity.
More on approximating the number of distinct elements - applications of hashing to streaming |

May 24 |
Basics of streaming algorithms: approximating the number of distinct elements, frequency moments estimation |

May 17 |
Introduction to streaming and sublinear algorithms. |

May 11 |
Applications of embeddings to algorithm design. The Linial-London-Rabinovitch algorithm for SPARSEST-CUT. |

May 10 |
Proof of Bourgain's theorem for finite metric spaces |

May 6 |
Introduction to Finite Metric Spaces. Bourgain's theorem |

Apr 28 |
Primal-dual approximation algorithms: using LPs without solving them |

Apr 27 |
More on classical approximation algorithms: PTAS & FPTAS, classes of optimization approximation problems |

Apr 20 |
SDP relaxations: the Goemans-Williamson algorithm |

Apr 19 |
An overview of the Ellipsoid Algorithm: correctness and running time. Elements of semi-definite programming |

Apr 13 |
More on the geometry of Linear Programming |

Apr 12 |
The geometry of linear programming: basic feasible solutions, an outline of the Simplex Algorithm |

Mar 30 |
Randomized rounding for the standard Set Cover relation. Derandomizing the obvious Max-k-SAT algorithm using the method of conditional expectations |

Mar 29 |
Two approximation algorithms for Set Cover: standard greedy algorithm, deterministic rounding |

Mar 23 |
An LP-based proof of the max-flow=min-cut theorem. Introduction to randomized rounding. |

Mar 22 |
A geometric proof of the Farkas Lemma |

Mar 16 |
More about LP-duality, Farkas lemma, optimizing over polytopes |

Mar 15 |
Geometry of polytopes, Linear programs, elements of LP-duality, the proof of the LP-duality theorem |

Mar 9 |
The proof of the max-flow min-cut theorem, more about reductions, Vertex Cover, 2-approximation of VC |

Mar 8 |
Flows, cuts, and matchings. Bipartite matching, reductions, examples, introduction to the max-flow min-cut theorem |

Mar 2 |
Optimization problems, introduction to approximation algorithms, greedy approximations of Makespan, on-line algorithms |

Mar 1 |
Linear space sequence alignment - space savings by combining Dynamic Programming and Divide and Conquer |

Feb 23 |
Classical algorithmic paradigms (review material): greedy algorithms and dynamic programming |

Feb 22 |
Introduction, class overview |