The matrix-chain multiplication problem. and a dynamic programming algorithm for

Question

The matrix-chain multiplication problem.

and a dynamic programming algorithm for it was presented (here werefer to the problem
of computing only the smallest possible number of scalarmultiplications, not an actual
schedule of multiplications that achieves it). Recall that thealgorithm by filling the entries
of a table C in a certain order. Show what the table C would
look like after you fill its entries when the input to the problemis 8, 3, 2, 19, 18, 7, i.e., there
are five matrices, the first of which is an 8 × 3 matrix, thesecond a 3 × 2, etc.
The matrix-chain multiplication problem.

and a dynamic programming algorithm for it was presented (here werefer to the problem
of computing only the smallest possible number of scalarmultiplications, not an actual
schedule of multiplications that achieves it). Recall that thealgorithm by filling the entries
of a table C in a certain order. Show what the table C would
look like after you fill its entries when the input to the problemis 8, 3, 2, 19, 18, 7, i.e., there
are five matrices, the first of which is an 8 × 3 matrix, thesecond a 3 × 2, etc.

Explanation / Answer

Dear User, The five matrices are                             M0   M1    M2    M3   M4                             8 x 3 , 3x 2, 2x19, 19x18, 18x7    No.ofmult                 No.ofmulti                No.ofmulti                 No.ofmulti                               M0                            (M0M1)                 (M0(M1M2))               (M0(M1(M2M3)))                                                                                        ((M0M1)M2)              (M0((M1M2)M3))                                                                                                           ((M0M1)(M2M3))                                                                                                           ((M0(M1M2))M3)                                                                                                         (((M0M1)M2)M3)                                         No.of multi                                      (M0(M1(M2(M3M4))))                  (M0 M1)     = 8 x 3 x 2     = 48 (M1M2) = 3x2x19 = 114 The order of the matrix is 3x19    (M0(M1M2)) = 8x3x19 = 456+114 = 570 The order of the matrix is 8x19 ((M0M1)M2) = 48 + (8x2x19) = 48 +304 = 352 The order of the matrix is 8x19 The order of the matrix is 8x19 (M2M3) = 2x19x18 = 684 (M1(M2M3))) =( 3 x2x18)+684 = 108+684 = 788 The order of the matrix is 3x18 (M0(M1(M2M3))) = (8x3x18)+788 =432+788 =1220 The order of the matrix is 8x18 Like this we can calculate the remaining matrices and fivevariable matrix multiplication      I hope this will helps toyou

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---