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:
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.
3. Using Floyds algorithm (See Algorithm2 slide 54), calculate the length of the shortest path between each pair of nodes in the graph by constructing a matrix. Give the each step of the adjacency matrix. see image.
Program Floyds algorithm and use the graph of problem 3 in a driver program to test you answer.