CSE 5311 Section 501 Fall 1998
Homework 3
Due: February 25, 1998, in class

1. Print out the table m created by performing the memoized version of matrix-chain on the sequence of dimensions 30, 35, 15, 5, 10, 20, 25.

   m is
        0 15750  7875  9375 11875 15125
        0     0  2625  4375  7125 10500
        0     0     0   750  2500  5375
        0     0     0     0  1000  3500
        0     0     0     0     0  5000
        0     0     0     0     0     0

2. Use the algorithm given in class to determine an LCS of (1,0,0,1,0,1,1,1) and (0,1,0,1,1,0,1,1,0).
3. Can the black-heights of nodes in a red-black tree be maintained as fields in the nodes of the tree without affecting the asymptotic performance of any of the red-black tree operations? Show how, or argue why not (this is Exercise 15.2-3).
4. Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(nW) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack (this is Exercise 17.2-2).
5. Generate a dynamic programming solution to the calculation of World Series odds. Compare the run time of your approach with the run time of the straightforward approach. In the World Series, two teams (A and B) are playing a match to see who is the first to win n games. Each team has a 50% chance of winning any game. The problem is to compute P(i,j), the probability that if A needs i games to win and B needs j games to win, that A will eventually win the match. For example, in the World Series, if the Dodgers have won two games and the Yankees have won one game, then i=2, j=3, and P(2,3) is 11/16.

   Note that if i=0 and j>0, then team A has already won and P(0,j) = 1. Similarly, P(i,0) = 0 for i>0. If i and j are both greater than 0, then P(i,j) must be the average of P(i-1,j) (the probability that A wins the match if it wins the next game) and P(i,j-1) (the probability that A wins the match if it loses the next game).

6. Consider the problem of constructing a minimum height binary search tree for an ordering sequence of keys (for example, 1, 2, 3, 4, 5) by choosing one key to be the root (for example, 3) and then recursively constructing trees for the keys to the left (1, 2 in this case) and right (4, 5 in this case) of the root. Show that this problem exhibits optimal substructure.

   In addition, consider a greedy solution that always choose the middle key of the sequence to be the root of the tree. Show that this greedy choice always appears in an optimal solution to the tree problem, although there may exist additional optimal solutions not containing the greedy choice.

• About this document ...