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

Matrix Dimension

A1 8 * 5

A2 5*10

A3 10*30

A4 30*20

A5 20*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 60 55

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

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

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

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