CSE 5311 Section 501 Fall 1998

**Homework 3**

Due: February 25, 1998, in class

- 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

- 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).
- 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).
- 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).
- 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).

- 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.

Wed Jan 28 17:13:40 CST 1998