Courses:

Advanced Algorithms >> Content Detail



Calendar / Schedule



Calendar

LEC #TOPICSKEY DATES
1Introduction
2LINEAR PROGRAMMING (LP): basic notions, simplex metho
3LP: Farkas Lemma, duality
Problem set 1 due
4LP: complexity issues, ellipsoid method
5LP: ellipsoid method
6LP: optimization vs. separation, interior-point algorithm
7LP: optimality conditions, interior-point algorithm (analysis)
8LP: interior-point algorithm wrap up

NETWORK FLOWS (NF)
Problem set 2 due
9NF: Min-cost circulation problem (MCCP)
10NF: Cycle cancelling algs for MCCP
11NF: Goldberg-Tarjan alg for MCCP and analysisProblem set 3 due
12

NF: Cancel-and-tighten

DATA STRUCTURES (DS): Binary search trees

13DS: Splay trees, amortized analysis, dynamic trees
14DS: dynamic tree operations
15

DS: analysis of dynamic trees

NF: use of dynamic trees for cancel-and-tighten

16APPROXIMATION ALGORITHMS (AA): hardness, inapproximability, analysis of approximation algorithmsProblem set 4 due
17AA: Vertex cover (rounding, primal-dual), generalized Steiner tree
18AA: Primal-dual alg for generalized Steiner tree
19AA: Derandomization
20AA: MAXCUT, SDP-based 0.878-approximation algorithm
21AA: Polynomial approximation schemes, scheduling problem: P||Cmax  
22AA: Approximation Scheme for Euclidean TSPProblem set 5 due
23AA: Multicommodity flows and cuts, embeddings of metricsProblem set 6 due

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.