Previous Year Questions: Dynamic Programming | Algorithms - Computer Science Engineering (CSE) PDF Download

Q1: Consider product of three matrices M₁, M₂ and M₃ 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 (M₁ M₂) M₃ than to compute M₁ (M₂M₃)?  (2020)
(a) Always take the same time
(b) (1/x + 1/z) < (1/w + 1/y)
(c) x > y
(d) (w + x) > (y + z)
Ans: (b)
Sol:

Cost of (M₁M₂) M_{3 =} wxy + wyz
while Cost of M₁ (M₂M₃) = xyz + wxz
Now, The time taken by (M₁M₂) M₃ will be less than M₁ (M₂M₃), when
wxy + wyz < xyz + wxz
Divide both sides with wxyz, we will get:


Q2: Assume that multiplying a matrix G₁ of dimension p x q with another matrix G₂ of dimension pxq requires pqr scalar multiplications. Computing the product of n matrices G₁G₂G₃...G_n can be done by parenthesizing in different ways. Define G_i G_i+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G₁G₂G₃G₄G₅G₆ using parenthesization (G₁(G₂G₃))(G₄(G₅G₆)), G₂G₃ and G₅G₆ are the only explicitly computed pairs. 
Consider a matrix multiplication chain F₁F₂F₃F₄F₅, where matrices F₁, F₂, F₃, F₄ and F₅ are of dimensions 2 x 25, 25 x 3, 3 x 16, 16 x 1 and 1 x 1000, respectively. In the parenthesization of F₁F₂F₃F₄F₅ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are    (2018)
(a) F₁F₂ and F₃F₄ only
(b) F₂F₃ only
(c) F₃F₄ only
(d) F₁F₂ and F₄F₅ only
Ans: (c)
Sol: If we multiply anything with F₅ we will get much greater multiplication cost because F₅ is 1 x 1000 matrix so 1000 will play vital role in cost. So we will multiply F₅ at very last step.
So, here is the sequence giving minimal cost:
(F₁(F₂(F₃F₄))) (F₅) = 48 +75 + 50 + 2000 = 2173
Explicitly computed pairs is (F₃F₄)
Correct Answer: C

Q3: Which of the following algorithms solves the all pair shortest path problem?  (2017)
(a) Prim's algorithm
(b) Dijkstra's algorithm
(c) Bellman ford algorithm
(d) Floyd warshalls algorithm
Ans: (d)
Sol: Option D will be correct...
Floyd warshalls algorithm is based on dynamic paradigm approach which is used to solve All pair shortest path problem..

Q4: Let A₁,A₂,A₃, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A₁A₂A₃A₄ using the basic matrix multiplication method is________.  (2016 SET-2)
(a) 1500
(b) 5000
(c) 1000
(d) 2000
Ans: (a)
Sol: 
Matrix Parenthesizing: A₁ ((A₂A₃)A₄)
Check my solution below, using dynamic programming

• A₁₂ = 10 × 5 × 20 = 1000
• A₂₃ = 5 x 20 x 10 = 1000
• A₃₄ = 20 x 10 x 5 = 1000

Answer is 1500.

Q5: The Floyd-Warshall algorithm for all-pair shortest paths computation is based on  (2016 SET-2)
(a) Greedy paradigm
(b) Divide-and-Conquerparadigm.
(c) Dynamic Programing paradigm.
(d) neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
Ans: (c)
Sol: In Floyd Warshall's, we calculate all possibilities and select best one so its neither Divide & Conquer nor Greedy but based on Dynamic Programming Paradigm.
Correct Answer: C

Q6: A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is________.       (2015 SET-2)
(a) 4  
(b) 5
(c) 6
(d) 7
Ans: (b)
Sol: The answer should be 5.

1. We first need to shift 2 in place of 1 keeping 5 AND 14 intact as it isn't mentioned in the question that the entire row elements move.
2.  4 is shifted up, next to 2 (keeping 12 and infinity intact in column 2).
3.  Now in second row 6 is shifted left.
4. 18 shifts up to the second row
5.  And finally 25 is shifted left to the third column.

So, this takes 5 moves and still maintains the tableau property. Also infinity is placed to the right of 25 and below 23 (unfilled entries to be filled with ∞). The final table would look as follows.


Q7: Consider two strings A ="qpqrr" and B="pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = _______.  (2014SET-2)
(a) 24
(b) 23
(c) 34
(d) 33
Ans: (c)
Sol: In first string, if we want to get 4 as maximum length then LCS should end with either "rr" or "qr".
Only 4 combinations are possible for LCS with length 4:
"qpqr", "qqrr","pqrr","qprr"
Now, check for matching sequences in second string, except for "qqrr" all are possible.

Q8: Four matrices M₁, M₂, M₃ and M4 are dimensions p x q, q x r, r x s and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example When multiplied as ((M₁ x M₂) × (M₃ x M₄) the total number of scalar multiplications is pqr + rst + prt. When multiplied as (((M₁ x M₂) × M₃) × M₄), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the minimum number of scalar multiplications needed is  (2011)
(a) 248000
(b) 44000
(c) 19000
(d) 25000
Ans: (c)
Sol: 
Ordering:

•  First Multiply M₂ X M₃.

This requires 100 x 20 x 5 multiplications.

•  Then Multiply M₁ x (M₂ M₃).

This requires 10 x 100 x 5 multiplications.

•  Then Multiply (M₁ x (M₂ × M₃)) × M₄.

This requires 10 x 5 x 80 multiplications.

Total 19000 Multiplications.
Brute Force approach - anyone can do.
No. of possible ordering for 4 matrices is C3 where C3 is the 3rd Catalan number and giver by
So, here we have
1. (M₁ x M₂) x (M₃ x M₄)
2. (M₁ × (M₂ × M₃)) × M₄
3. ((M₁ x M₂) x M3) x M₄
4. M₁ × (M₂ × (M₃ × M₄))
5. M₁ x ((M₂ x M₃) x M₄))
Each of these would give no. of multiplications required as
1. pqr + rst + prt
2. qrs + pqs + pst
3. pqr + prs + pst
4. rst + qrt + pqt
5. 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.
1. pqr + rst + prt = 20000 + 8000 + 16000 = 44000
2. qrs + pqs + pst = 10000 + 5000 + 4000 = 19000 - smallest value in choice, we can stop here.
3. 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

So, we can fill the following table starting with the diagonals and moving upward diagonally.
Here, k < j but ≥ i, mi, i] = 0.
P₀ = p = 10, P₁ = q = 100, P₂ = r = 20, p₃ =s = 5,p₄ = t = 80. P<sub>3

Our required answer is given by m [1, 4] = 19000.</sub>

Q9: An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array

Which of the following statements is TRUE?  (2011)
(a) The algorithm uses dynamic programming paradigm
(b) The algorithm has a linear complexity and uses branch and bound paradigm
(c) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(d) The algorithm uses divide and conquer paradigm.
Ans: (a)
Sol: The algorithm is storing the optimal solutions to subproblems at each point (for each i), and then using it to derive the optimal solution of a bigger problem. And that is dynamic programming approach. And the program has linear time complexity.
Now, branch and bound comes when we explore all possible solutions (branch) and we backtrack as soon as we realise we won't get a solution (in classical backtracking we will retreat only when we won't find the solution). In backtracking: In each step, you check if this step satisfies all the conditions.
If it does: you continue generating subsequent solutions
If not you go one step backward to check for another path
So, backtracking gives all possible solutions while branch and bound will give only the optimal one.
The given algorithm here is neither backtracking nor branch and bound. Because we are not branching anywhere in the solution space.
And the algorithm is not divide and conquer as we are not dividing the problem and then merging the solution as in the case of merge sort (where merge is the conquer step).

Q10: A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence (LCS) of x[m] and Y[n] as I(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of x[m] and Y[n] is given below:

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N = n+1, such that L[i,j] = I(i,j).
Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?  (2009)
(a) All elements L should be initialized to 0 for the values of l(i,j) to be properly computed.
(b) The values of I(i,j) may be computed in a row major order or column major order of L(M,N).
(c) The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N).
(d)  L[p, q] needs to be computed before L[r, s] if either p
Ans: (b)
Sol: expr2 = max (l (i - 1, j), l (i, j - 1))
When the currently compared elements doesn't match, we have two possibilities for the LCS,
one including X[i] but not Y[j] and other including Y[j] but not X[i].

Answer is B. Dynamic programming is used to save the previously found LCS. So, for any index [p, q] all smaller ones should have been computed earlier. Option D is not correct as the condition given requires even L[3, 2] to be computed before L [2, 4] which is not a necessity if we follow row-major order.


Q11: A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence (LCS) of x[m] and Y[n] as I(m, n), where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of x[m] and Y[n] is given below:

Which one of the following options is correct?  (2009)
(a) expr1 = l(i-1, j) + 1
(b) expr1 = l(i, j-1)
(c) expr2 = max(l(i-1, j), l(i,j-1))
(d) expr2 = max(l(i-1, j-1), l(i, j))
Ans: (c)
Sol: Answer is C. When the currently compared elements doesn't match, we have two possibilities for the LCS, one including X[i] but not Y[j] and other including Y[j] but not X[i].


Q12: Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?   (2008)
(a) Dynamic programming
(b) Backtracking
(c) Greedy
(d) Divide and Conquer
Ans: (a)
Sol: Answer is (A) because Floyd Warshall algorithm is used to find all shortest paths which is a dynamic programming approach.

Q13: The subset-sum problem is defined as follows. Given a set of n positive integers, S={a₁, a₂,..., a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W +1 columns. X[i,j], 1 ≤ i ≤ n, 0 ≤ j ≤ W, is TRUE if and only if there is a subset of {a₁, a₂,..., a_i}whose elements sum to j.
Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?  (2008)
(a) X[1,W]
(b) X[n,0]
(c) X[n,W]
(d) X[n-1,n]
Ans: (c)
Sol: If LAST ROW and LAST COLUMN entry is 1, then there exists a subset whose elements sum to W.

Q14: The subset-sum problem is defined as follows. Given a set of n positive integers, S={a₁, a₂,..., a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X[i, j], 1 ≤ i ≤ n, 0 ≤ j ≤ W, is TRUE if and only if there is a subset of {a₁, a₂,..., a_i}whose elements sum to j.
Which of the following is valid for 2 ≤ i ≤ n and a_i ≤ j ≤ W?  (2008)
(a) X[i, j] = X[i - 1, j] V X[i, j - a_i]
(b) X[i, j] = X[i - 1, j] V X[i -1, j - a_i]
(c) X[i, j] = X[i - 1, j] ∧ X[i, j - a_i]
(d) X[i, j] = X[i - 1, j] ∧ X[i - 1,j - a_i]
Ans: (b)
Sol: This is analogous to the dynamic programming solution to 0/1 knapsack problem.
Consider the capacity of the knapsack, i.e., W to be analogous to J(the total sum here).
The solution exploits the optimal substructure of the problem.
At each stage we can have 2 options:
Case (1): Either we take an item(in this question either we consider the element A_i) along with the total solution to previous sub-problem(total solution here means the total sum obtained till previous sub-problem) in which case we choose A[i-1][j - ai]
A[i-1] indicates we are considering solution to previous subproblem and
A[j - a_i] means we have considered element a_i and now remaining sum is J - a_i which has to be further considered.
Case (2): Or we do not consider the item(in this case the element a_i) in which case we only consider the solution to previous subproblem, which is, A[i - 1][J]
Since the whole solution to this subset-sum problem is Logical OR(+) of cases 1 and 2, we eliminate options C and D because both are considering the Logical and of the two parts of the solution.
Now, since here in the given question we are given a boolean array X[n] [W + 1]
So, an entry X[i][j] is true only if sum j is possible with array elements from 0 to i.
So, for Each element of array, a, we consider two possibilities:
(1) Either we can ignore it and still get our possible sum, which is, X[i - 1][j]
OR
(2) We could include element a, and then get our required sum, which is, X[i - 1][j - a_i] And finally, to get X[i][j], we take logical or of the above two cases.
Hence, answer is option B.

Q15: Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).
Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?  (2007)
(a) 2⁹
(b) 2¹⁹
(c)
(d)
Ans: (d)
Sol: Say, r = Move Right and u = Move Up
so using 10 combination of r and 10 combinations of u moves we get a solution.
Convert the graphical moves to text and one such solution we get,
= {u, u, u, u, u, u, u, u, u, u, r, r, r, r, r, r, r, r, r, r}
now all possible arrangements of them is given by =
now we need to discard the segment move from (4, 4) to (5, 4):
to do that we first calculate how many solutions to our problem to reach (10, 10) involves that segment.
We'll then subtract those solutions from the total number of solutions.
Number of solutions to reach from(0, 0) to (4, 4),
=all possible arrangements of {r, r, r, r, u, u, u, u}
=
definitely we take the segment (4, 4)to (5, 4) = 1.
now, Number of solutions to reach from (5, 4) to (10, 10),
= all possible arrangements of {r, r, r, r, r, u, u, u, u, u, u}
=
so required number of solutions for
i.e. = (20/10) - (8/4) x 1 x (11/5)

Q16: Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i, j) then it can move to either (i +1,j) or (i, j +1).
How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?  (2007)
(a)
(b) 2²⁰
(c) 2¹⁰
(d) None of the above
Ans: (a)
Sol: In ques given, r = Move Right and u = Move Up
so using 10 combination of r and 10 combinations of u moves we get a solution
Convert the graphical moves to text and one such solution we get,
= {u, u, u, u, u, u, u, u, u, u, r, r, r, r, r, r, r, r, r, r}
now all possible arrangements of them is given by =
Hence, option A is true.

Q17:  Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?  (1998)
(a) Dynamic programming
(b) Backtracking
(c) Greedy
(d) Divide and Conquer
Ans: (a)
Sol: Answer is (A) because Floyd Warshall algorithm is used to find all shortest paths which is a dynamic programming approach.