5,486 views
1 votes
1 votes
What is the minimum number of multiplications required to compute the chain of matrices A = A1.A2.A3.A4 with size of A1 is 10x100, A2 is 100x5, A3 is 5x50, and A4 is 50x1?

2 Answers

Best answer
8 votes
8 votes

This problem can be solved by Dynamic Programming, because of the property that there are overlapping subproblems.Means we are computing same thing over and again if we follow tree method.

$\color{MidnightBlue}{(i,j)} \color{blue}{\rightarrow}$ Minimum number of scalar multiplications required to find $A_{i}A_{i+1}.....A_{j}$

$A_{1} = 10*100, A_{2} = 100*5, A_{3} = 5*50$ and $A_{4} = 50*1$

Here, All unique sub-problems are $\Rightarrow$ $\color{green}{(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}$. And we are intereseted in finding $(1,4)$ (minimum scalar multiplications to compute  $A_{1}A_{2}A_{3}A_{4}$)

$\color{blue}{(1,1) = (2,2) = (3,3) = (4,4) = 0}$ (Base case)

$\color{green}{(1,2) = 10*100*5 = 5000, (2,3) = 100*5*50 = 25000}$ and $\color{green}{(3,4) = 5*50*1 = 250}$ And Dimensions of $A_{1}A_{2} , A_{2}A_{3}$ and $A_{3}A_{4}$ are $10*5, 100*50, 5*1$ respectively.

So,far table looks like :

$(1,3) = min\Bigg\{\begin{align*}
(1,1) + (2,3) &+ 10*100*50  \\
(1,2) + (3,3) &+  10*5*50\\
\end{align*}$

$\color{olive}{(1,3) = min\Bigg\{\begin{align*}
0+ 25000 &+ 50000  \\
5000 + 0 &+ 2500\\
\end{align*}  =7500}$


$(2,4) = min\Bigg\{\begin{align*}
(2,2) + (3,4) &+ 100*5*1  \\
(2,3) + (4,4) &+  100*50*1\\
\end{align*}$

$\color{olive}{(2,4) = min\Bigg\{\begin{align*}
0 + 250&+ 500  \\
25000 + 0 &+  5000\\
\end{align*} = 750}$

At this point, Table looks like :

We are just $1-step$ away from final result that is computing $(1,4)$ by using table above.

$\color{navy}{(1,4) = min\Bigg\{\begin{align*}
(1,1) + (2,4) &+ 10*100*1  \\
(1,2) + (3,4) &+  10*5*1\\
(1,3) + (4,4) &+  10*50*1
\end{align*}}$


$\color{navy}{(1,4) = min\Bigg\{\begin{align*}
0 + 750 + 1000  \\
 5000 + 250 +  50\\
7500 + 0+  500
\end{align*} = 1750}$


We got our answer to be $\color{teal}{1750}$ and Our Table looks like :

selected by
1 votes
1 votes
A 1= 10 * 100

A2 = 100 * 5

A3 = 5 * 50

A4 = 50 * 1

(A1(A2(A3A4))) gives the optimal ans which is 1750...

I have done multiplication of A3A4 first since it will reduce the new dimensions..

So new dimensions say A5 from A3A4 = 5*1 and result is (5*50*1) = 250

Next I have choice for A1A2 and A2A5...

A2A5 reduces dimensions and gives optimal results ...result will be (100*5*1) and new dimensions say for A6 = 100 * 1

Now for A1A6 = 10*100*1

So total = 250 + 500 + 1000 = 1750

Related questions

0 votes
0 votes
1 answer
1
soorajchn asked Mar 14, 2015
5,500 views
a) n- ( lg(n)) - 2b) n + (lg(n)-2)
1 votes
1 votes
1 answer
3
0 votes
0 votes
2 answers
4
sh!va asked Jan 27, 2017
541 views
What is the minimum number of wires required in serial communication?a. 4b. 2c. 3d. 8