Please do not answer if you are not familiar with Algorithms Design a greedy alg
ID: 672813 • Letter: P
Question
Please do not answer if you are not familiar with Algorithms
Design a greedy algorithm for the matrix chain multiplication problem. You must clearly highlight the greedy property used by your algorithm. Your algorithm must do better in terms of number of subproblems it solves and time complexity than the dynamic programming algorithm. Does your algorithm always lead to an optimal solution? If not, present a counter example.
I know that dynamic algorithm gives the best solution for matrix chain multiplication, but I need to do Matrix chain multiplication with greedy algorithm
Explanation / Answer
You can solve it using greedy solution but it will not optimal i mean it will not have time complexity less than the dynamic programming.
Let us understand with an example
Suppose we have 3 matrix of size (3x2); (2x3) and (4x3);
Greedy Solution will pick first two matrix and multiple it to get a matrix of (3x3) and then this resultant matrix is multiplied with (4x3) to produce (4x3) final matrix where as in Dynamic Programming we can check for all case and pick the optimal out of all here the optimal is multiply (4x3) and (3x2) first and then resultant with (2x3) [optimal solution];
so Greedy Solution :- Start with Cheapest adjacent pair but it will not be always true as shown in above example.