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