COMP-362: Honours Algorithm Design

Fall 2009

Lecture topics and suggested readings

Lecture 1 (1 September):

Course introduction

A tour through course ideas as illustrated by Shotgun DNA sequencing and Shortest Common Superstring

Lecture 2 (3 September):

Intro to dynamic programming

Fibonacci, Making Change, Longest Common Subsequence

Read KT 6.2 and KT 6.6 (Sequence alignment is very similar to LCSubSeq)

Lecture 3 (8 September):

Optimal triangulation of a convex polygon

Optimal binary search trees (Read CLRS 15.5 if you want to learn more)

Read KT 6.4 and KT 6.5 for more examples

Lecture 4 (10 September):

Shortest paths (Bellman-Ford)

Testing for the presence of negative weight cycles

Read KT 6.8 and KT 6.10

Lecture 5 (15 September):

Advanced dynamic programming techniques

Hirschberg’s trick (space efficiency): read KT 6.7

Exploiting sparseness (time efficiency)

Lecture 6 (17 September):

Greedy algorithms for set selection

Matroids

Read CLRS 16.4

Lecture 7 (22 September):

Intro to linear programming

Duality

Read CLRS 29.1, 29.2 and 29.3 (can omit proof of strong duality for now)

Lecture 8 (24 September):

Intro to flows and cuts

Read KT 7.1 and 7.2

Lecture 9 (29 September):

Two proofs that max-flow=min-cut

Ford-Fulkerson algorithm

Lecture 10 (1 October):

Edmonds-Karp and Dinitz improvements

Matchings

Hall’s Theorem

Read KT 7.3, 7.5

Lecture 11 (6 October):

            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)

Lecture 12 (8 October):

Simplex algorithm

For a more formal presentation, see CLRS 29.3

See also notes on WebCT

Lecture 13 (13 October):

Simplex example (see slides)

Proof of strong duality

Comparison of simplex and Ford-Fulkerson for max-flow

Lecture 14 (15 October):

More on duality:

Interpretation of the dual

LP and dual LP for shortest path

Lecture 15 (20 October):

Circuit evaluation by linear programming

Circuit-SAT

Definition of NP

Read KT 8.1, 8.2

Lecture 16 (22 October):

Cook-Levin Theorem

NP-completeness of 3-SAT and Independent Set

Read KT 8.3, 8.4.

For further enjoyment, read Aaronson’s lecture notes.

Lecture 17 (27 October):

NP-completeness of Clique, Vertex Cover, Hamiltonian Cycle, Travelling Salesman and 3d Matching

Read KT 8.2, 8.5.

Lecture 18 (29 October):

Problem session (Anil Ada)

Lecture 19 (3 November):

Midterm

Lecture 20 (5 November):

NP-completeness of Zero-One Equations, Integer Linear Programming, k-Coloring

Read KT 8.6, 8.7

Lecture 21 (10 November):

co-NP: Read KT 8.8, 8.9, 8.10

Backtracking

Branch and Bound

Lecture 22 (15 November):

Introduction to approximation algorithms

Greedy algorithm for set cover: KT 11.3

LP rounding approach to set cover: KT 11.6

Lecture 23 (17 November):

2-approximation of metric TSP

Inapproximability of general TSP

Arbitrarily good approximation of knapsack: KT 11.8

Knapsack and the cosmological constant (unexamined material)

Lecture 24 (19 November):

Fixed parameter tractability

Searching for small vertex covers

Definition of tree-width

Tree-width of control flow graphs

Lecture 25 (24 November):

Edge separation property in tree decompositions

Linear time algorithm for max weight independent set in graphs with bounded tree-width

Lecture 26 (26 November):

Finish proof that max wt indep set recurrence is correct

Graph properties expressible using monadic second order logic

Finding tree decompositions