COMP-362: Honours Algorithm Design

Fall 2011

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 (6 September):

Intro to dynamic programming

Fibonacci, Optimal triangulation of a convex polygon

Read KT 6.2, 6.4, 6.5 (RNA secondary structure has similarities with triangulation)

Lecture 3 (8 September):

Shortest paths (Bellman-Ford)

Testing for the presence of negative weight cycles

Read KT 6.8 and KT 6.10

Lecture 4 (13 September):

Advanced dynamic programming techniques (using Longest Common Subsequence as an example)

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

Read KT 6.8 and KT 6.10

Lecture 5 (15 September):

Additional advanced DP: Exploiting sparseness (time efficiency)

Introduction to matroids

Lecture 6 (20 September):

Matroids: proof that greedy works

Transversal 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 (27 September):

Linear programming duality for fractional knapsack

Intro to flows and cuts

Read KT 7.1 and 7.2

Lecture 9 (29 September):

Linear programming dual of max-flow is min-cut

Lecture 10 (4 October):

Ford-Fulkerson algorithm

Edmonds-Karp (fat pipes)

Read 7.3

Lecture 11 (6 October):

Dinitz (short pipes)

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)

Lecture 12 (11 October):

Baseball elimination (KT 7.12)

Hall’s theorem (KT 7.5)

Konig-Egervary theorem