Lecture Notes for CS 512, Algorithm Design

10 April 2000, Some Dynamic Programming Problems

1. longest common substring

   1. Z a subsequence of X

   2. Z a common subsequence of X and Y

   3. find the longest common substring of X and Y

   4. the brute force algorithm: consider all substrings of X

   5. what are the subproblems

      1. arbitrary division doesn't work - optimal problems are not optimal

      2. nibbling off the ends does work - subproblems are optimal

   6. a recursive implementation is still exponential - but there are only |X||Y| subproblems

   7. from that we can get a dynamic-programming solution

2. optimal polygon triangulation

   1. polygon, side, vertex, chord, triangulation

   2. a weight function over triangles

   3. factor the polygon P into triangles so as to minimize the sum of the triangle weights

   4. the brute force algorithm: consider all triangulations of P

   5. optimal triangulation subproblems are optimal in combination

   6. a recursive implementation is still exponential - but there are only polynomially many subproblems

   7. a dynamic-programming solution

   8. the analogy between triangulation and matrix chains

This page last modified on 5 April 2000.