COMP-362: Honours
Algorithm Design
Fall 2008
Lecture topics and suggested readings
September
2:
(Claude Crépeau) Dynamic programming
September
4:
(Claude Crépeau) Dynamic programming
Based on CLRS 15.2, 15.3, 15.4.
Recommend reading KT 6.1-6.7.
September
9:
Course intro (slightly delayed)
Computational complexity of the
landscape of string theory vacua
Approximating 0-1 knapsack: KT 11.8.
September
11:
Shortest paths (review)
Bellman-Ford and detecting negative
cost cycles
Read KT 6.8, 6.9. Also KT 4.4 if you
don’t remember Dijkstra.
Independent set in trees. (See KT
10.2 for a different approach.)
September
16:
(David Avis) Theoretical framework
for greedy algorithms: matroids.
September
18:
Intro to linear programming
Read Jeff
Ericsson’s notes on linear programming.
(You aren’t responsible for the proof of strong duality
unless we cover it in class later.)
September
23:
Max-flow and min-cut
LP formulations
Interpretation of the dual as
min-cut
September
25:
Direct proof of max-flow/min-cut
theorem
Ford-Fulkerson algorithm
Read KT 7.1, 7.2
September
30:
Edmonds-Karp algorithm
Bipartite matching and disjoint
paths
Hall’s theorem
Read KT 7.3, 7.5
October
2:
Disjoint paths and Menger’s theorem
(KT 7.6)
Circulations (KT 7.7)
Applications:
Survey design (KT 7.8)
Image segmentation (KT 7.10)
Project selection (KT 7.11)
Baseball elimination (KT 7.12)
October
7:
Simplex algorithm and strong duality
Read section 6 of these notes for
the detailed proof of strong duality
Sections 3 and 4 provide another
take on simplex.
You aren’t responsible for Farkas and simplex tableaux.
October
9:
Simplex part II.
Interpretation of max-flow simplex:
connection to Ford-Fulkerson.
Circuit evaluation as LP.
October
14:
Intro to NP-completeness.
Cook-Levin, Circuit-SAT, 3-SAT.
Read KT 8.1, 8.3, 8.4.
For further enjoyment, read Aaronson’s lecture
notes.
October
16:
NP-completeness of Independent Set,
Vertex Cover, Clique, Hamiltonian Cycle, Travelling Salesman.
Read KT 8.2, 8.5.
October
21:
NP-competeness of 3d-Matching, ILP,
ZOE, Knapsack, Subset-Sum,
Read KT 8.6
October
23:
Perceptrons and LP
NP-completeness of training a 3-node
neural network
October
28:
Midterm
October
30:
NP-completeness of k-Colorability
Backtracking plus branch-and-bound
Comments on midterm
Read KT 8.7
November
4:
(David Avis) Approximation
algorithms for Vertex Cover
From greedy, matching and LP
rounding
Read KT 11.4 and 11.6
November
6:
More approximation algorithms:
Greedy and LP rounding for Set Cover
Greedy for k-Clustering
Metric TSP from MST
Read KT 11.3
November
11:
Inapproximability of TSP
PCP theorem
Bounding approximation of MAX3SAT
Based on Gupta’s
notes.
November
13:
Bounding approximation of Vertex
Cover using PCP
Intro to fixed-parameter
tractability:
Vertex Cover in time
O(f(k)p(n))
Read KT 10.1, 10.2
November
18:
Tree decompositions of graphs
Independent Set for graphs of
bounded tree-width
Read KT 10.4
November
20:
Finish Independent Set
Sources of low tree-width graphs.
Building tree decompositions
Comments about final exam
November
25:
PSPACE
Definition and complete problems
Read KT chapter 9
November
27:
P plus time travel = PSPACE
Based on an article by Aaronson and Watrous