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)

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,

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

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

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

November 20:

Finish Independent Set

Sources of low tree-width graphs.

Building tree decompositions

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