My algorithms professor is asking us to go through these notes and understand dynamic programing matrix chain multiplication. I need help understanding the formula in the red box and what each of the letters are or represent. 68 DESIGN OF EFFICIENT ALGORITHMS2.8where the dimensions of each M, are shown in the brackets. Evaluating Min the orderM₁ X (MX (M3 × M₁))requires 125.000 operations, while evaluating M in the order(M, X (MM;)) × M₁requires only 2200 operations. ☐Trying all possible orderings in which to evaluate the product of n matricesso as to minimize the number of operations is an exponential process (see Ex-ercise 2.31), which is impractical when n is large. However, dynamic program-ming provides an O(n³) algorithm. Let m₁, be the minimum cost of computingM₁ × Mi+1 × ·× M; for 1 ≤ i ≤ j ≤n. Clearly,(0,if i=j(2.9)mij =(MIN (mik + M+1, +1-1),if j>iish i, is theminimum, taken over all possible values of k between i and j- 1, of the sumof these three terms.The dynamic programming approach calculates the m₁'s in order of in-creasing difference in the subscripts. We begin by calculating m₁ for all i,then mi,i+1 for all i, next mi,i+2, and so on. In this way, the terms m₁ and mk+1,jin (2.9) will be available when we calculate mij. This follows since j - i mustbe strictly greater than either of k-i and j― (k+1) if k is in the range i ≤k 2.8 DYNAMIC PROGRAMMINGRecursive techniques are useful if a problem can be divided into subproblemswith reasonable effort and the sum of the sizes of the subproblems can bekept small. Recall from Theorem 2.1 that if the sum of the sizes of the sub-problems is an, for some constant a > 1, the recursive algorithm is likely tobe polynomial in time complexity. However, if the obvious division of a prob-lem of size n results in n problems of size n - 1, then a recursive algorithm islikely to have exponential growth. In this case a tabular technique calleddynamic programming often results in a more efficient algorithm.In essence, dynamic programming calculates the solution to all subprob-lems. The computation proceeds from the small subproblems to the largersubproblems, storing the answers in a table. The advantage of the methodlies in the fact that once a subproblem is solved, the answer is stored andnever recalculated. The technique is easily understood from a simple example.Consider the evaluation of the product of n matricesM = M₁x M₂ × · · · × M„where each M, is a matrix with 1-1 rows and r; columns. The order in whichthe matrices are multiplied together can have a significant effect on the totalnumber of operations required to evaluate M, no matter what matrix multi-plication algorithm is used.Example 2.7. Assume that the multiplication of a p× q matrix by a q× rmatrix requires pqr operations, as it does in the "usual" algorithm. and con-sider the productM =M₁[10 × 20]M2[20 x 50]M3[501]MA(2.8)[1 × 100]

The Formula: mij=MINi≤k<j(mik+mk+1,j+ri−1rkrj)ifj>i and =mij=0ifi=j Explanation:…

68 DESIGN OF EFFICIENT ALGORITHMS 2.8 where the dimensions of each M, are shown in the brackets. Evaluating M in the order M₁ X (MX (M3 × M₁)) requires 125.000 operations, while evaluating M in the order (M, X (MM;)) × M₁ requires only 2200 operations. ☐ Trying all possible orderings in which to evaluate the product of n matrices so as to minimize the number of operations is an exponential process (see Ex- ercise 2.31), which is impractical when n is large. However, dynamic program- ming provides an O(n³) algorithm. Let m₁, be the minimum cost of computing M₁ × Mi+1 × ·× M; for 1 ≤ i ≤ j ≤n. Clearly, (0, if i=j (2.9) mij = (MIN (mik + M+1, +1-1), if j>i ish i, is the minimum, taken over all possible values of k between i and j- 1, of the sum of these three terms. The dynamic programming approach calculates the m₁'s in order of in- creasing difference in the subscripts. We begin by calculating m₁ for all i, then mi,i+1 for all i, next mi,i+2, and so on. In this way, the terms m₁ and mk+1,j in (2.9) will be available when we calculate mij. This follows since j - i must be strictly greater than either of k-i and j― (k+1) if k is in the range i ≤ k 1, the recursive algorithm is likely to be polynomial in time complexity. However, if the obvious division of a prob- lem of size n results in n problems of size n - 1, then a recursive algorithm is likely to have exponential growth. In this case a tabular technique called dynamic programming often results in a more efficient algorithm. In essence, dynamic programming calculates the solution to all subprob- lems. The computation proceeds from the small subproblems to the larger subproblems, storing the answers in a table. The advantage of the method lies in the fact that once a subproblem is solved, the answer is stored and never recalculated. The technique is easily understood from a simple example. Consider the evaluation of the product of n matrices M = M₁x M₂ × · · · × M„ where each M, is a matrix with 1-1 rows and r; columns. The order in which the matrices are multiplied together can have a significant effect on the total number of operations required to evaluate M, no matter what matrix multi- plication algorithm is used. Example 2.7. Assume that the multiplication of a p× q matrix by a q× r matrix requires pqr operations, as it does in the "usual" algorithm. and con- sider the product M = M₁ [10 × 20] M2 [20 x 50] M3 [501] MA (2.8) [1 × 100]