Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is 5, 10, 3, 12, 7, 50, 6. Show the table and choice of k used to ll each cell in the table. 5. Problem 15-1 (p. 404) 6. Design a dynamic programming algorithm to solve the 0-1 knapsack problem. As a reminder, in this problem there are n items, the i-th item has value v and weight w , where v and w are positive i i i i integers (i = 1,...,n). A thief wants to maximize the value of what he steals, but he cannot carry more than W pounds in his knapsack, where W is an integer. He must take all of an item or none of it. What is the maximum value that the thief can steal? Hint: Consider any xed order of the items. For arbitrary i and p, let C[i,p] be the maximum total value of any subset of the rst i items whose total weight is at most p. To compute C[i,p], the thief has two choices when considering item i: either he takes or he leaves it behind

If he takes the i-th item, then he gets the value of the item but the item also takes up some of the capacity of the knapsack for the previous items to use.

If he doesn't take the i-th item, then he doesn't get the value of the item, so all the capacity of the knapsack is available for previous items.

(a) Which element(s) of C hold, or are needed to compute, the nal answer?

(b) Which element(s) of C hold the basis element(s) and how should they be lled in?

(c) What is the formula for lling in each of the other (non-basis) elements of C?

(d) In what order should the elements of C be lled in?

(e) What is the running time of the algorithm and why?

(f) How can the actual set of items to steal be determined? (Just give a brief high-level description.)