(Solved by Humans)-1. Use the dynamic programming technique to find an optimal

Question

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

1. 2.?Using?Floyd?s?algorithm,?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.???

both question and the diagram is in the word doc

COSC 3333

HW4

Homework 4
Due Date: 5/5/2016 11:59pm
1. Use the dynamic programming technique to find an optimal parenthesization of
a matrix-chain product whose sequence of dimensions is &lt;5, 8, 4, 10, 7, 50, 6&gt;.
Matrix
A1
A2
A3
A4
A5
A6

Dimension
5*8
8*4
4*10
10*7
7*50
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. Using Floyd?s algorithm, 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.
Floyd?s algorithm
function Floyd(L(1?n,1?n]):array[1?n,1?n]
array D[1?n,1?n]
D =L
for k=1 to n do
for i=1 to n do
for j=1 to n do
D[i,j]=min(D[i,j], D[i,k]+D[k,j])
return D

COSC 3333

HW4

B

15
A
10

50

10
10
30

10
5

E
5

F

40

15

20

G
50
20

C
10

D