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