1. This question refers to the Matrix Chain Multiplication as discussed in class. (a) Refine the algorithms MATRIXCHAIN MULT from the lecture notes such that in addition to the table mij (which stores the cost of the optimal bracketing) you also fill in a data structures that stores the actual optimal bracketing. You decide what s is, within the constraints that (a) it has to be usable for the process of performing the actual multiplication, and (b) your refined MATRIXCHAIN MULT must maintain the original O(n³) running time. Explain how the structure s can be used afterward. Provide an argument for the correctness of your algorithm and explain how the original running time is maintained. (b) Give a recursive algorithm MATRIXCHAIN MULTIPLY(M, s, i, j) that actually performs the optimal matrix-chain multiplication M; × × M;. The inputs are the chain M = ... (M1, M2,..., Mn) of matrices to be multiplied, the structures returned by the algorithm that you developed for Question 1a, and the two indices i and j, 1 ≤ i ≤ j ≤ n. The call MATRIXCHAIN MULTIPLY(M, s,1,n) will thus optimally multiply the whole chain of matrices. Assume that MATRIXMULTIPLY(A, B) returns the product of the two matrices A and B.
1. This question refers to the Matrix Chain Multiplication as discussed in class. (a) Refine the algorithms MATRIXCHAIN MULT from the lecture notes such that in addition to the table mij (which stores the cost of the optimal bracketing) you also fill in a data structures that stores the actual optimal bracketing. You decide what s is, within the constraints that (a) it has to be usable for the process of performing the actual multiplication, and (b) your refined MATRIXCHAIN MULT must maintain the original O(n³) running time. Explain how the structure s can be used afterward. Provide an argument for the correctness of your algorithm and explain how the original running time is maintained. (b) Give a recursive algorithm MATRIXCHAIN MULTIPLY(M, s, i, j) that actually performs the optimal matrix-chain multiplication M; × × M;. The inputs are the chain M = ... (M1, M2,..., Mn) of matrices to be multiplied, the structures returned by the algorithm that you developed for Question 1a, and the two indices i and j, 1 ≤ i ≤ j ≤ n. The call MATRIXCHAIN MULTIPLY(M, s,1,n) will thus optimally multiply the whole chain of matrices. Assume that MATRIXMULTIPLY(A, B) returns the product of the two matrices A and B.
Related questions
Question
question 1
Transcribed Image Text:1. This question refers to the Matrix Chain Multiplication as discussed in class.
(a) Refine the algorithms MATRIXCHAIN MULT from the lecture notes such that in addition
to the table mij (which stores the cost of the optimal bracketing) you also fill in a data
structures that stores the actual optimal bracketing. You decide what s is, within
the constraints that (a) it has to be usable for the process of performing the actual
multiplication, and (b) your refined MATRIXCHAIN MULT must maintain the original O(n³)
running time.
Explain how the structure s can be used afterward. Provide an argument for the
correctness of your algorithm and explain how the original running time is maintained.
(b) Give a recursive algorithm MATRIXCHAIN MULTIPLY(M, s, i, j) that actually performs the
optimal matrix-chain multiplication M; × × M;. The inputs are the chain M =
...
(M1, M2,..., Mn) of matrices to be multiplied, the structures returned by the algorithm
that you developed for Question 1a, and the two indices i and j, 1 ≤ i ≤ j ≤ n. The
call MATRIXCHAIN MULTIPLY(M, s,1,n) will thus optimally multiply the whole chain of
matrices. Assume that MATRIXMULTIPLY(A, B) returns the product of the two matrices A
and B.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
