1. Use the dynamic programming technique to find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <5, 8, 4, 10, 7, 50, 6>.

Matrix Dimension

A1 5*8

A2 8*4

A3 4*10

A4 10*7

A5 7*50

A6 50*6

You may do this either by implementing the MATRIX-CHAIN-ORDER algorithm in the text or by simulating the algorithm by hand. In either case, show the dynamic programming tables at the end of the computation.

2. We have 5 objects, and the weights and values are

No. 1 2 3 4 5 w 10 20 30 40 50 v 20 30 66 40 60

The knapsack can carry a weight not exceeding 100, find a subset items and give the total weight and value for following algorithms:

1) By using the algorithm of greedy of value for 0-1 knapsack problem? By selecting the highest value first.

2) By using the algorithm of greedy of weight for 0-1 knapsack problem? By selecting lightest item first.

3) By using the algorithm of greedy of density for 0-1 knapsack problem? By selecting the highest density item first.

4) By using the algorithm of greedy of density for fractional knapsack problem? By selecting the highest density item first.