Table of contents
1.
Introduction
2.
Gate questions on Dynamic Programming
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

GATE Questions on Dynamic Programming- Part 1

Author Muskan Gupta
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

Frequently Asked Questions

  1. What is the Dynamic Programming Approach? 
    Dynamic programming is an approach for optimizing recursive solutions when recursive calls happen on the same input repeatedly. The idea is quite simple, store the result that needs to calculate again and again to use it.  
     
  2. What are the different types of dynamic programming approaches?
    There are generally two types of approaches:
    Top-Down Approach: In this approach, we break the bigger problem into smaller subproblems. 
    Bottom-Up Approach: In this approach, we join the smaller subproblem, to find the solution to a bigger problem.
     
  3. What are overlapping subproblems?
    A problem has overlapping subproblems if it can be divided into smaller problems for reusing multiple times.
     
  4. What is an optimal substructure?
    A problem has an optimal substructure if the optimal solution can be obtained from optimal solutions of its subproblems.
     
  5.  What problem of recursion does DP solve?
    Recursion risks solving identical subproblems numerous times. This inefficiency is managed and fixed by dynamic programming.

Conclusion

In this article, we have gone through important previous years' gate questions on Dynamic Programming (Dynamic Programming). 

Related Links:

Check out this problem - Minimum Coin Change Problem 

We hope that this blog has helped you enhance your knowledge regarding Dynamic programming and if you would like to know more about the preparation strategy of the gate, check out our article on How to prepare in the Last 10 days to score high in GATE?. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass