Algorithm Design

Fall 2013

ITCS @ IIIS, Tsinghua University
Instructor: Periklis A. Papakonstantinou []
Teaching assistant: Yicheng Liu
Lectures: Monday 1.30-4.05pm (3x45min) at TX117
Office hours: Monday 13.30-4.05pm (or by appointment), FIT 4-608-7


[Dec 25] Assignment 8 is out and the deadline is December 29th (it consists only of 1 problem)

This Monday (December 30th) we will have the final exam (starting at 1.30pm).
Venue: Teaching Building 5, Room# 5205

Handouts, problem-sets, and links


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 Bipartite Matching.
Sep 30 Beautiful duality: Max-flow, Min-cut, duality arguments, Ford-Fulkerson.
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