** **

**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