Introduction
Dynamic Programming is a technique of doing an optimization over recursion. We store the answer for the overlapping subproblems and use that result if we need the answer for the same problem in the future. Hence, we save the time of re-computing the answer for the same problem. It is a great technique that helps us to reduce the exponential time complexity to polynomial time complexity.
You can check out our top dynamic programming problems.
This blog covers the previous year's gate questions on Dynamic Programming( related to the topic of dynamic programming).
Gate questions on Dynamic Programming
1. The approach of Dynamic Programming is used.
(A) When an optimal solution is needed
(B) When the solution has optimal substructure
(C) When the given problem can be reduced to the 3-SAT problem
(D) Because Dynamic Programming is faster than Greedy
Answer: (B)
Explanation:
Algorithms other than Dynamic Programming can also give optimal solutions. So, Option (A) is incorrect.
Option (D) is wrong because Greedy algorithms are usually faster than Dynamic programming.
2. An algorithm used to find the length of the longest monotonically increasing sequence consisting of numbers in a given array A[0: n-1] is shown as follows. Here Li denotes the size of the longest monotonically increasing sequence that starts at index 'i' in the given array.
Initialize Ln-1 = 1.
For all i such that 0 ≤ i ≤ n-2
Which of the following statements is NOT FALSE?
(A) The algorithm uses a dynamic programming paradigm
(B) The algorithm has non-linear polynomial complexity, and it uses branch and bound paradigm
(C) The algorithm has linear complexity, and it uses branch and bound paradigm
(D) The algorithm uses the divide and conquer paradigm.
Answer- (A)
Explanation- The algorithm uses a dynamic programming paradigm; that's why the correct answer is Option A. The Longest Increasing Subsequence (LIS) problem is generally used to find the length of the longest possible subsequence of a provided sequence. All subsequence elements are sorted in ascending order.
For example :
A[] = {5, 10, 2, 1, 15,18}
Output: Length of LIS = 4.
The longest increasing subsequence is 5, 10, 15, and 20. Here, We can see many subproblems in the above recursive solution, which are solved repeatedly. So, We can say that this problem has the overlapping substructure property, and re-computation of the same subproblems can be avoided by either the memorization method or tabulation method. If the problem is closely observed, then we can convert this problem to the Longest Common Subsequence type Problem. Initially, we will create another array of unique elements of the original array and sort it. Here, the longest increasing subsequence of our array must be there as a subsequence in our sorted array. Our problem is now decreased to finding the common subsequence between the two arrays. Hence the correct answer is that The algorithm uses a dynamic programming paradigm.
3. Four matrices Mat1, Mat2, Mat3, and Mat4 of dimensions pxq, qxr, rxs, and sxt, respectively, can be multiplied with different numbers of total scalar multiplications. For example, when multiplied as ((Mat1 X Mat2) X (Mat3 X Mat4)), the total number of multiplications is pqr + prt + rst. When multiplied as (((Mat1 X Mat2) X Mat3) X Mat4), the total number of scalar multiplications is pqr + pst + prs. If the value of p = 10, q = 100, r = 20, s = 5, t = 80, then the number of scalar multiplications required is (2016 gate questions on Dynamic Programming)
(A)44000
(B)25000
(C)248000
(D)19000
Answer: (D)
Explanation:
It is based on matrix chain multiplication problem. We get the minimum number of multiplications using ((Mat1 X (Mat2 X Mat3)) X Mat4). Total number of multiplications = 100x20x5 (for Mat2 x Mat3) + 10x100x5 + 10x5x80 = 19000.
Source - gateoverflow.com
4. Let A, B, C, and D be four matrices having sizes 10 x 5, 5 x 20, 20 x 10, 10 x 5, sequentially. What will be the minimum number of scalar multiplications needed to find the product ABCD using the primary matrix multiplication method is (2016 gate questions on Dynamic Programming)
(A) 2000
(B) 1500
(C) 100
(D) 500
Answer: (B)
Explanation: We have various ways to perform matrix chain multiplication because matrix multiplication is associative. No matter how the product is parenthesized, the result of the matrix chain multiplication obtained will remain the same. Now, we have four matrices, A, B, C, and D, and we would have:
((AB)C)D = ((A(BC))D) = (AB)(CD) = A((BC)D) = A(B(CD)).
Although, the order in which the product is parenthesized affects the efficiency because the number of simple arithmetic operations needed to calculate the product also changes. Here, A is a 10 × 5 matrix, B is a 5 x 20 matrix, C is a 20 x 10 matrix, and D is 10 x 5.
If we multiply two matrices, X and Y have an order of l x m and m x n, respectively, then the total number of scalar multiplications in the multiplication of X and Y will be lxmxn.
Then, The total number of scalar multiplications needed in the following sequence of matrices will be :
A((BC)D) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500.
All other parenthesized options will require several multiplications of more than 1500.
5. Consider the list of weights and values of items given below. Note that every item has only one unit.
| Item number | Weight(in Kgs) | Value(in Rupees) |
| 1 | 10 | 60 |
| 2 | 7 | 28 |
| 3 | 4 | 20 |
| 4 | 2 | 24 |
The task is to choose a subset of these items such that their total value is maximized and the total weight is at most 11 Kg. Additionally, items can't be split. Opt_V denotes the total value of items chosen by an optimal algorithm. A greedy algorithm sorts the items concerning their value-weight ratios in decreasing order and greedily packs them, beginning from the first item in the ordered list. The greedy algorithm's total value of items chosen is denoted by greedy_V.
The value of Opt_V − greedy_V is ______.
Note –It was in the section of the numerical type question.
(A) 8
(B) 16
(C) 60
(D) 44
Answer: (B)
Explanation:
| Item No | Weight | Value | Value/Weight |
| 1 | 10 | 60 | 6 |
| 2 | 7 | 28 | 4 |
| 3 | 4 | 20 | 5 |
| 4 | 2 | 24 | 12 |
After sorting:
| Item No | Weight | Value | Value/Weight |
| 4 | 2 | 24 | 12 |
| 1 | 10 | 60 | 6 |
| 3 | 4 | 20 | 5 |
| 2 | 7 | 28 | 4 |
First, we will pick item_4 (The highest value-weight ratio). The second highest is item_1, but it cannot be chosen because of its weight. Now, item_3 shall be selected.
item_2 cannot be involved because of its weight.
Therefore, overall profit by greedy_V = 20+24 = 44
Hence, Opt_V − greedy_V = 60-44 = 16
So, answer is 16.
6. The Floyd-Warshall algorithm for finding all-pair shortest paths is based on (2016 GATE Question on DP)
(A)Greedy algorithm
(B)Divide and Conquer algorithm
(C)Dynamic Programming
(D)None of these
Answer: (C)
Explanation: The Floyd-Warshall algorithm uses dynamic programming.
To know more about this algorithm, visit the Floyd-warshall algorithm.
7. Which of the following paradigm could be used to find the solution to the problem in minimum time: We have a set of non-negative integers and a value K. Check if there exists a subset of the specified set whose sum is equal to K:(2018 gate questions on Dynamic Programming)
(A)Divide and Conquer
(B)Greedy algorithm
(C)Branch and Bound
(D)Dynamic programming
Answer: (D)
Explanation: The given problem is a Subset-sum problem with a
set of non-negative integers, and a value called sum is given to check if there exists a subset of the specific set whose sum is the same as the given
sum. With the recursion technique, the time complexity of the above problem is exponential. We can solve such type of problem in pseudo-polynomial time using Dynamic programming.
8. Consider the strings A = "babcc" and B = "abacbca". Let p be the length of the longest common subsequence (not necessarily contiguous) between A and B and let q be the number of such longest common subsequences between A and B. Then 10q + p = ___.
(A)33
(B)43
(C)34
(D)23
Answer: (C)
Explanation: The LCS is of length 4. There are 3 LCS of length 4 "bacc", "abcc" and "babc".
A subsequence is basically a sequence that can be obtained from another sequence by selecting zero or more elements without changing the remaining elements' order. Subsequences need not be contiguous. Since the length of given strings A = "babcc" and B = "abacbca" are very small, we don't need to build a 5×7 matrix and solve it using dynamic programming. Instead, we can solve it manually just by brute force. We will first check if there exists a subsequence of length 5 since min_length(A, B) = 5.
Since there is no subsequence, we will now check for length 4. "bacc", "abcc", and "babc" are common in both strings.
p = 4 and q = 3
p + 10q = 34
9. Consider a sequence T00 defined as :
T00(0) = 1, T00(1) = 1
T00(x) = 10 ∗ T00(x – 1) + 100
T00(x – 2) for x ≥ 2
Then the value of set of T00 is what ?
(A) (1, 110, 1200)
(B) (1, 110, 600, 1200)
(C) (1, 2, 55, 110, 600, 1200)
(D) (1, 55, 110, 600, 1200)
Answer: (A)
Explanation:
T00(0) = 1, T00(1) = 1
T00(n) = 10 ∗ T00(n – 1) + 100
T00(2) = 10 * T00(1) + 100
= 10 * 1 + 100
= 10 + 100
= 110
Similarly:
T00(3) = 10 * T00(2) + 100
= 10 * 110 + 100
= 1100 + 100
= 1200
The sequence will be (1, 110, 1200).
So, (A) will be the answer.
10. What is the technique of storing the previously calculated values in dynamic programming called?
(A) Memorization
(B)Mapping
(C)Saving value property
(D)Storing value property
Answer: (A)
Explanation:
The technique under which the previously calculated values are stored, so that, these values can be used to solve other subproblems, is called memorization.
Refer to Gate Questions on Dynamic Programming: Part 1 and Gate Questions on Dynamic Programming: Part 3 for more questions. Also, check out the Gate Syllabus for CSE.
84+ registered