Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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 2

Author Muskan Gupta
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. What is the Dynamic Programming Approach? 
    Dynamic programming is an approach for optimizing recursive solutions when recursive calls repeatedly happen on the same input. The idea is quite simple: store the result that needs to be calculated again and again.  
     
  2. Write 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?
    If a problem has overlapping subproblems, it can be divided into smaller problems for reuse 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. Write the difference between DP and recursion?
    Recursion is the foundation of logic, the call stack, local variables, etc. It utilizes a logic-driven intuitive cognitive approach. During interviews, one of the most prevalent reasons individuals want to comprehend recursion is frequently asked.
    And, Dynamic Programming (DP) is an algorithmic technique for solving a problem optimally by breaking it down into simpler subproblems and utilization of the information that the optimal solution to the whole problem relies upon the optimal solution to its subproblems

Conclusion

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

We hope that this blog has helped you enhance your knowledge regarding gate questions on Dynamic Programming and if you would like to learn more, check out our articles on Gate books for CSE. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
GATE Questions on Dynamic Programming- Part 1
Next article
GATE Questions on Dynamic Programming - Part 3
Live masterclass