CSC 344
Homework 4

Due April 22, to be done singly or in pairs.

Assigned April 1.
You've each been given a dynamic-programming problem to solve. Design a solution and implement it in a real programming language.

• Problem 3-2 algorithm, Diaz & Zelenovic
• Problem 3-4, Skrbic & Oide
• Problem 3-5 O(n)-time algorithm, Huang & Oh
• Problem 3-6 (b), Hessen & Lavalle
• Problem 3-7 (b), Budhram & Drofa
• Longest Common Subsequence, Smith & Goulbourne
• Minimum Weight Triangulation, Modi

Assigned April 8.
Do problems 4-2, 4-4, 4-7, 4-10, 4-11, 4-12, 4-13 from the textbook. (Note: most of these can be solved by using standard tools like depth-first search, breadth-first search, Kruskal's or Prim's algorithm, Dijkstra's algorithm, and Floyd-Warshall's algorithm, essentially as subroutines to your algorithm. If you're familiar with those, it should take you only two or three hours. If not, you will be familiar with them by the end of the assignment :-)

Choose one of the algorithms in problems 4-7, 4-10, 4-11, 4-12, 4-13, and implement it in a real programming language.