# Dynamic Programming

 Question 1
Consider product of three matrices $M_{1}$,$M_{2}$ and $M_{3}$ having w rows and x columns, x rows and y columns, and y rows and z columns. Under what condition will it take less time to compute the product as $\left(M_{1} M_{2}\right) M_{3}$ than to compute $M_{1}\left(M_{2} M_{3}\right)$ ?
 A Always take the same time B $(1 / x+1 / z) \lt (1 / w+1 / y)$ C $x \gt y$ D $(w+x) \gt (y+z)$
ISRO CSE 2020   Algorithm
Question 1 Explanation:
 Question 2
Assume that multiplying a matrix G1 of dimension pxq with another matrix G2 of dimension pxq requires pqr scalar multiplications. Computing the product of n matrices G1G2G3...Gn can be done by parenthesizing in different ways. Define Gi Gi+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using parenthesization (G1(G2G3))(G4(G5G6)), G2G3 and G5G6 are the only explicitly computed pairs. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2x25, 25x3, 3x16, 16x1 and 1x1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
 A F1F2 and F3F4 only B F2F3 only C F3F4 only D F1F2 and F4F5 only
GATE CSE 2018   Algorithm
Question 2 Explanation:

 Question 3
Which of the following algorithms solves the all pair shortest path problem?
 A Prim's algorithm B Dijkstra's algorithm C Bellman ford algorithm D Floyd warshalls algorithm
ISRO CSE 2017   Algorithm
Question 3 Explanation:
 Question 4
Let A1,A2,A3, and A4 be four matrices of dimensions 10x5, 5x20, 20x10, and 10x5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is __________.
 A 1500 B 5000 C 1000 D 2000
GATE CSE 2016 SET-2   Algorithm
Question 4 Explanation:
 Question 5
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on