Week 1: Greedy Algorithms

Jan 3 (lecture): Interval scheduling, Minimum Spanning Tree, started Clustering to maximize distance between clusters. Correspond to sections 4.1 and 4.5 of Kleinberg-Tardos [KT].
Jan 4 (tutorial): Scheduling to minimize lateness (sec. 4.2 of [KT]); machine minimization scheduling (sec. 4.1 of [KT]).
Jan 5 (lecture): Finished clustering, Huffman codes for data compression (sections 4.7 and 4.8 in [KT]). A summary of Huffman code with formal proofs.

Week 2: Dynamic Programming

Jan 10 (lecture): Fibonacci numbers, weighted interval scheduling, longest common subsequence. A summary of longest common subsequence.
Jan 11 (tutorial): minimum knapsack, maximum independent set in trees (sections 6.4 and 6.7 here).
Jan 12 (lecture): Edit distance, shortest path with negative weights (Bellman-Ford). Quiz 1.

Week 3: End of Dynamic Programming; Maximum Flow

Week 4: Extensions and Applications of Maximum Flow; Randomized Algorithms

Jan 24 (lecture): extensions and applications of maximum flow (undirected graphs, Menger's theorem, node-capacitated flow, image segmentation).
Jan 25 (tutorial): applications of maximum flow. Reduction from maximum bipartite matching to max flow (slides here); any d-regular bipartite graph can be decomposed into d perfect matchings (proof here). By the way of proving the above result, we also proved Hall's Theorem.
Jan 26 (lecture): Randomized algorithms: exact 3SAT; Monte Carlo/Las Vegas algorithms; Karger's algorithm for global min-cut. Quiz 2. Summary of Karger's algorithm available here.

Week 5: Finish randomized algorithms, start Linear Programming.

Jan 31 (lecture): finish Karger's algorithm; hashing; fingerprinting.
Feb 1 (tutorial): Randomized Load Balancing and Balls and Bins; Monty Hall problem.
Feb 2 (lecture): perfect matching in bipartite graphs and polynomial identity testing; start Linear Programming.

Week 6: Finish Linear Programming

Feb 7 (lecture): applications of Linear Programming (fitting a hyperplane; linear classifier; hinge loss); start LP-duality. Recipe for computing dual LP's.
Feb 8 (tutorial): computing canonical form of LP's; max flow, min-cost flow and shortest path via Linear Programming.
Feb 9 (lecture): LP-duality - applications to max flow/min cut. Integrality gap of linear programs; how to use the Ellipsoids method with separation oracle to solve large LP's and their duals.

Week 7: Midterm; finish LP-duality; NP-hardness

Feb 14: midterm
Feb 15 (tutorial): LP-duality - computing the dual; multicommodity flow and multicut; flow-cut gap.
Feb 16 (lecture): LP-duality for 0-sum games and minimax theorem; polynomial reductions, NP-hardness: Independent Set, Vertex Cover, Set Cover, SAT.

Week 8: NP-hardness; Approximation Algorithms

Feb 21 (lecture): definition of classes P and NP; definition of NP-completeness; Cook-Levin theorem; NP-completeness of 3SAT and 3-coloring.
Feb 22 (tutorial): NP-hardness of: 3D-matching; 0/1 equations; Subset Sum; if time left, Hamiltonian Cycle and Traveling Salesperson Problem.
Feb 23 (lecture): Approximation Algorithms: greedy approximation algorithms for Vertex Cover and Set Cover; Traveling Salesperson Problem: hardness of approximation for the non-metric version and a factor-2 approximation for the metric version via MST's.

Week 9: finish Approximation Algorithms

Feb 28 (lecture): Approximation Algorithms via LP-rounding: weighted Vertex Cover; Node-Disjoint Paths. Will revisit LP-relaxations and integrality gaps. Quiz 3.
March 1 (tutorial): approximation algorithms: Load Balancing, Machine Minimization scheduling, Max Coverage.
March 2 (lecture): Randomized LP-rounding approximation algorithms: weighted Set Cover, Congestion Minimization.

Week 10

March 7 (lecture): Probabilistically Checkable Proofs (PCP's) and their connection to hardness of approximation; online algorithms; streaming algorithms.
March 8 (tutorial): additional examples of randomized algorithms.