Assignment

Note: Not all problems are graded. Some of the ungraded ones might appear later in quizzes or tests. Submit your own work although you may discuss ideas with your peers.

Assignment 4: Dynamic Programming

Out: 09/20/04. Due: 10/09/04.

Exercise 15.2-1. Implement a program to solve the MATRIX CHAIN MULTIPLICATION problem.
Exercise 15.4-1, Exercise 15.4-2, Exercise 15.4-4.
Implement programs to solve the LONGEST COMMON SUBSSEQUENCE problems.
- Sequences from Section 15.4: X sequence and Y sequence. Sample output: output
- Sequences from biology: sequence 1 sequence 2. Sample output: output
Exercise 15-1. Implement a program to solve the BITONIC TRAVELING SALESPERSON problem.
Experiment with a simple graphical 2-dimensional I/O representation. See a sample Java applet.
Exercise 15-3. Implement a program to solve the MINIMUM EDIT DISTANCE problem.
Sample output: output (without kill and twiddle).
Exercise 15-4. Implement a program to solve the PARTY problem.
Input file convention: each line begins with the identity of a person or node in the tree, followed by its conviviality rating, followed by the identities of its children. So the number of lines equals the number of nodes in the tree hierarchy.
Sample input (see Figure 10.10 in text) with a sample output.