Register

MadeEasy Test Series: Algorithms - Dynamic Programming

• edited by
1,843 views
1 1 vote

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?

1 Answer

Best answer
2 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
Voting & Accepting an answer helps improve the community
← Previous · TURING MACHINENext → · Connectivity(4-10)-N...
← Previous in category · Regarding the comple...Next in category → · #Algorithms Time Com...
Position:
Show:

Related questions

0 0 votes
0 0 answers
995
995 views
adityaaswal asked Nov 30, 2018
995 views
MadeEasy Subject Test 2019: Algorithms - Dynamic Programming
Let G = (V,E) be a directed graph.Each edge of G is represented as (i,j) with length l[i,j].If there is no edge from i to j then l[i,j] = (IMAGE ATTACHED)
0 0 votes
0 0 answers
658
658 views
Shamim Ahmed asked Nov 26, 2018
658 views
MadeEasy Test Series : Algorithms - Dynamic Programming
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...
3 3 votes
2 answers 2 answers
3.2k
3.2k views
talha hashim asked Aug 1, 2018
3,248 views
MadeEasy Test Series: Algorithms - Dynamic Programming
Consider two strings A = “abbaccda” and B = “abcaa” consider "x"be length of the longest common subsequence between A and B and “y” be the number of distinct such longest...
2 2 votes
1 1 answer
2.9k
2.9k views
Sumaiya23 asked Jan 29, 2018
2,885 views
MadeEasy Test Series 2018: Algorithms - Dynamic Programming
The number of balance parenthesis possible with 5-pairs of parenthesis _________. [ Assume ( ) and (( )) is balance parenthesis but not ) ( ]