Answer is C.
Ordering:
- First Multiply $M_2 \times M_3.$
This requires $100*20*5$ multiplications.
- Then Multiply $M_1 \times (M_2 \times M_3).$
This requires $10*100*5$ multiplications.
- Then Multiply $(M_1 \times (M_2 \times M_3)) \times M_4.$
This requires $10*5*80$ multiplications.
Total $19000$ Multiplications.
Brute Force approach - anyone can do.
No. of possible ordering for 4 matrices is $C_3$ where $C_3$ is the $3^{rd}$ Catalan number and given by $n=3$ in $\frac{1}{n+1} {}^{2n}C_n = 5.$
So, here we have
- $(M_1 \times M_2) \times (M_3 \times M_4)$
- $(M_1 \times (M_2 \times M_3)) \times M_4$
- $((M_1 \times M_2) \times M_3) \times M_4$
- $M_1 \times (M_2 \times (M_3 \times M_4))$
- $M_1 \times ((M_2 \times M_3) \times M_4))$
Each of these would give no. of multiplications required as
- $pqr + rst + prt $
- $qrs + pqs + pst$
- $pqr + prs + pst$
- $rst + qrt + pqt$
- $qrs + qst + pst$
The last 2 are having $qt$ terms which are the highest terms by far and hence we can avoid them from consideration $qt = 8000$ multiplied by one other term would be larger than any value in choice. So, just find the value of first 3 terms.
- $pqr + rst + prt = 20000 + 8000 + 16000 = 44000$
- $qrs + pqs + pst = 10000 + 5000 + 4000 = 19000$ - smallest value in choice, we can stop here.
- $pqr + prs + pst$
Dynamic Programming Solution (should know Matrix Chain Ordering algorithm)
Here we have a chain of length 4.
Dynamic programming solution of Matrix chain ordering has the solution
$ m[i, j] = \begin{cases} 0 &\text{ if } i=j\\ \displaystyle \min_{i\leq k < j } m[i][k] + m[k+1][j] + p_{i-1}p_{j}p_{k} &\text{ if } i < j\end{cases}$
So, we can fill the following table starting with the diagonals and moving upward diagonally. Here, $k < j$ but $\geq i, m[i,i] = 0.$
$p_0=p = 10, p_1 = q = 100, p_2=r = 20, p_3 = s =5, p_4 = t =80. $
$$\scriptsize \begin{array}{|l|l|l|l|l|} \hline \text{} & \textbf{j=1} & \textbf{j=2} & \textbf{j=3} & \textbf{j=4}\\\hline
\textbf{i=1} & \text{0} & \text{$p_0p_1p_2$} & \min(m[1,1]+m[2,3]+p_0p_1p_3,& \min(m[1,1]+m[2,4]+ p_0p_1p_4, \\
&&=20000&\quad m[1,2]+m[3,3]+p_0p_2p_3 )&\quad m[1,2]+m[3,4]+p_0p_2p_4, \\
&&&=15000&\quad m[1,3]+m[4,4]+p_0p_3p_4)\\&&&& = 19000
\\\hline
\textbf{i=2} & \text{} & \text{0} & p_1p_2p_3 = 10000 & \min(m[2,2]+m[3,4]+p_1p_2p_4,\\
&&&&\quad m[2][3]+m[4,4]+p_1p_3p_4)\\
&&&&= \min(160000, 50000)=50000
\\\hline
\textbf{i=3} &\text{} & \text{} & \text{0} &p_2p_3p_4 = 8000 \\\hline \textbf{i=4} &\text{} &\text{} & \text{} & \text{0} \\\hline \end{array}$$
Our required answer is given by $m[1,4] = 19000.$