1. Consider the following procedure that performs multiplication of two rectangular matrices A[1..1][1..m] and B[1..m][1..n]: MATRIX_MULTIPLY (A[1..[][1..m], B[1..m][1..n]) Run-time per instruction Frequency for i 1 to 1 for 1. 2. 3.

4. 5. 6. j1 to n Cij ←0 for k1 to m Cij ← Cij + aik bkj C₁ C₂ C3 C4 C5 C6 return C (a) Fill in for each line of instruction, the number of times (i.e., frequency) the instruction is executed. (b) Derive the expression for the run-time of MATRIX_MULTIPLY in terms of l, m, n, and C₁, C₂, C3, C4, C5, and C6. In your expression, you should group together all the coefficients of the same term 1¹.m³.nk, where i, j, k are constants. For example, if the run-time expression is C4lm+G+n+C5lm+Can+C₂, we group the co- efficients of 1¹m¹nº (or Im) together, the coefficients of lºmºn' (or n) together, and the coefficients of lºmºnº (or 1) together. Note that each of I'm'nº, lºmºn', and lºmºnº involves the parameters "describing" the problem, i.e., 1, m, and n. The final expression should be (C4+C5)lm+(+C6)n+(+C₂).