Design and Analysis of Algorithms208010 marksNumerical: matrix chain multiplicationGreedy Algorithms vs Dynamic Programming, Recursion vs Dynam
Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order 2, 3, 4, 2, 5.
Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order $2, 3, 4, 2, 5$. [10]
Aspect Dynamic Programming Greedy Strategy --------------------------------------------- Global optimality Guarantees a globally optimal solution by examining all relevant subproblem combinations May settle for a locally optimal choice that is not globally optimal Subproblem reuse Solves each ove...