edited by
873 views
1 votes
1 votes

Consider two Person (Person X, Person Y). Person X who was given a problem to calculate A1 × A2 × A3 with dimension 3 × 100, 100 × 2 and 2 × 2 in minimum multiplication. Person X is the knows only Greedy algorithm (multiply matrix which gives less number of multiplication) and solve A1 × A2 × A3 with M1 multiplications. Person Y solved the same problem using Dynamic algorithm with M2multiplications. How many number of multiplications saved by Person Y than Person X?

edited by

1 Answer

Best answer
2 votes
2 votes
With Greedy algorithm, the order of multiplication is:

$A_{1}(A_{2}A_{3})$ , therefore the number of multiplications is $400 + 600 = 1000$

With dynamica programming which always picks the optimal order, the order is:

$(A_{1}A_{2})A_{3}$ , therefore the number of multiplications is $600 + 12 = 612$

Hence, Person Y would save $388$ multiplications.
selected by

Related questions

0 votes
0 votes
0 answers
1
Shamim Ahmed asked Nov 26, 2018
379 views
Which of the following procedure is suitable to find longest path from given vertex to any other vertex in Directed Acyclic Graph?Answer: Dynamic Programming.Why Greedy A...
2 votes
2 votes
1 answer
3
Sumaiya23 asked Jan 29, 2018
2,095 views
The number of balance parenthesis possible with 5-pairs of parenthesis _________. [ Assume ( ) and (( )) is balance parenthesis but not ) ( ]
0 votes
0 votes
0 answers
4