Introduction
Dynamic Programming is a recursion-based optimization approach. We save the answers to the overlapping subproblems and apply them again if the same problem arises in the future. As a result, we save time by not having to recalculate the answer to the same problem. It's a fantastic strategy for turning exponential time complexity into polynomial time complexity.
You can check out our top dynamic programming problems.
This blog covers the previous year's gate questions on Dynamic Programming(dynamic programming).
Gate questions on Dynamic Programming
Following are the previous year's gate questions on Dynamic Programming(dynamic programming).
1. Kadane algorithm is generally used to find out:(2017 gate questions on Dynamic Programming)
(A) Maximum sum subsequence present in an array
(B) Maximum sum subarray present in an array
(C) Maximum product subsequence present in an array
(D) Maximum product subarray present in an array
Answer - (B)
Explanation - Kadane algorithm is used to find out the maximum sum subarray present in an array. It runs in O(n) time complexity
2. Match the following:
List 1 |
List 2 |
(P) Prim's algorithm for minimum spanning tree | (i) Backtracking |
(Q) Floyd-Warshall algorithm for all-pairs shortest paths | (ii) Greedy method |
(R) Mergesort | (iii) Dynamic Programming |
(S) Hamiltonian circuit | (iv) Divide and conquer |
A) P - i, Q - ii, R - iv, S - iii
B) P - iii, Q - ii, R - iv, S - i
C)P - ii, Q - i, R - iii, S - iv
D)P - ii, Q - iii, R - iv, S - i
Answer- (D)
Explanation:
P) Prim's algorithm for minimum spanning trees is a greedy method.
Q) Floyd-Warshall algorithm for all-pairs shortest paths uses dynamic programming.
R) Mergesort uses Divide and conquer method.
S) Hamiltonian circuit uses the backtracking method.
3. Which of the standard algorithms shown below is not based on Dynamic Programming? (2017 gate questions on Dynamic Programming)
(A) Prim's Minimum Spanning Tree
(B) Bellman-Ford Algorithm for single-source shortest path
(C) Floyd Warshall Algorithm for all-pairs shortest paths
(D) 0-1 Knapsack problem
Answer- (A)
Explanation: Prim's Minimum Spanning Tree is a standard algorithm based on the Greedy Algorithm. All others are dynamic programming based.
4. The problem related to subset-sum is defined as follows. A set consisting of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and a positive integer W is given. Is there a subset of S , the sum of whose elements is W? A dynamic program for solving this problem uses a two-dimensional Boolean array Y, with n rows and W+1 columns. Y[i, j], 1 <= i <= n, 0 <= j <= W, will be true if there is a subset of {a1 ,a2 ,…,ai} the sum of whose elements is j. Which of the following is valid for ai <= j<= W and 2 <= i <= n?
(A) Y[i, j] = Y[i – 1, j] ∧ Y[i, j – ai]
(B) Y[i, j] = Y[i – 1, j] ∨ Y[i – 1, j – ai]
(C) Y[i, j] = Y[i – 1, j] ∧ Y[i -1, j – ai]
(D) Y[i, j] = Y[i – 1, j] ∨ Y[i, j – ai]
Answer: (B)
Explanation: Y[I, j] (ai <= j <= W and 2 <= i <= n ), is correct if either 1) is true or 2)
1) Sum of weights including ai is equal to j, i.e., if Y[i-1, j-ai] is accurate
so that we get ai +(j – ai) as j
2) Sum of weights excluding ai is equal to j, i.e., if Y[i-1, j] is true.
5. In the above question, which entry of the array Y, if TRUE, implies that there is a subset whose elements sum to W?
(A) Y[1, W]
(B) Y[n -1, n]
(C) Y[n ,0]
(D) Y[n, W]
Answer: (D)
Explanation: If we get the entry Y[n, W] as true, then there is a subset of {a1, a2, an} that has a sum as W.
To learn about the subset-sum problem, visit our Subset Sum Problem blog.
6.A sub-sequence of a given sequence can be defined as the given sequence with some elements (possibly none or all) were left out. We are given sequences, X[m] and Y[n], having lengths, m, and n, respectively, with X and Y indexes that start from 0.
We would like to find the length of the longest common subsequence(LCS) of A[m] and B[n] as l(m,n), where an incomplete definition for the recursive function l(i,j) to compute the length of The LCS of A[m] and B[n] is given as:
l(i,j) = 0, if either j=0 or i=0
= expression1, if i,j > 0 and X[i-1] = Y[j-1]
= expression2, if i,j > 0 and X[i-1] != Y[j-1] ( 2009 gate questions on Dynammic Programming)
(A) expression1 ≡ l(i-1, j) + 1
(B) expression1 ≡ l(i, j-1)
(C) expression2 ≡ max(l(i-1, j), l(i, j-1))
(D) expression2 ≡ max(l(i-1,j-1),l(i,j))
Answer: (C)
Explanation: In Longest common subsequence problem, there exists two
situations for X[0..i] and Y[0..j]
1) The last characters of the two strings are the same.
The length of LCS is the same as the length of LCS of Y[0..i-1] and X[0..j-1]
2) The last characters are not the same.
The length of LCS is maximum of following values of LCS
a) Longest Common Subsequence of Y[0....i-1] and X[0..j]
b) LCS of Y[0....i] and X[0..j-1]
7. Consider the both sequences given below:
P = < B, C, D, C, A, B, C >, and
Q = < C, A, D, B, C, B >
What will be the longest common subsequence's length of P and Q?
(A)2
(B)3
(C)5
(D)4
Answer: (D)
Explanation:
The concept is simple.
If there is a match between characters then dp[i,j]=dp[i-1,j-1]+1
If not, then dp[i,j]=max(dp[i-1,j],dp[i,j-1])
Calculation:
lenM= size of P
lenN= size of Q
Taking a matrix dp[lenN+1][lenM+1]
LCS(Longest Common Subsequence) table:
X⇨ | B | C | D | C | A | B | C | |
Y ⇩ |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
C | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
A | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
D | 0 | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
B | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
C | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
B | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
8. What happens when a top-down approach to dynamic programming is applied to a problem?
(A) It increases both the time and space complexity
(B) It decreases the time complexity and increases the space complexity
(C) It decreases the space complexity and increases the time complexity
(D) It decreases both the time and space complexity
Answer: (B)
Explanation: As the mentioned approach uses the memoization technique, it always stores the previously calculated values. Due to this, the time complexity decreases, but the space complexity increases.
9. Consider the product of three matrices L, M, and N having a rows and b columns, b rows and c columns, c rows and d columns. In which of the following conditions,
It will take less time to calculate the product as (LM)N than to calculate L(MN)?
(A) a>b
(B)(1/b + 1/d) < (1/a + 1/c)
(C) (a+b)>(c+d)
(D) It will take the same time in every condition
Answer: (B)
Explanation:
Order of L = a*b
Order of M = b*c
Order of N = c*d
For cost of (LM)N = abc + acd. Detailed steps are as follows:
Cost of LM = a * b* c
This gives us a new matrix. Let the new matrix be X.
Order of X is a * c.
Cost of XN = a * c * d
Total cost = LM cost + XN cost
Similarly , cost of L(MN) = bcd + abd
For (LM)N to take less time than L(MN)
(abc + abd ) < (bcd + abd)
On dividing both the sides of above equation , we get
(1/b + 1/d) < (1/a + 1/c )
10. Which of the features that are written below is a feature of a dynamic programming problem?
(A) Greedy approach
(B) Both optimal substructure and overlapping subproblems
(C) Optimal Substructure
(D) Overlapping subproblems
Answer: (B)
Explanation: A problem that could be solved using dynamic programming is supposed to have overlapping subproblems and optimal substructure properties.
Read More - Time Complexity of Sorting Algorithms
Refer to Gate Questions on Dynamic Programming: Part 2 and Gate Questions on Dynamic Programming: Part 3 for more questions. Also, check out the Gate Syllabus for CSE.