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