** **

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