Previously Asked Problems of Dynamic Programming on GATE

Q1. [GATE-CS-2016]
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

(A) Greedy Paradigm
(B) Divide-and-Conquer Paradigm
(C) Dynamic Programming Paradigm
(D) Neither Greedy nor Divide-and- Conquer nor Dynamic Programming Paradigm

Ans: (C) Dynamic Programming Paradigm

Q2. [GATE-CS-2015]

List-I

A. Prim’s algorithm for minimum spanning tree
B. Floyd-Warshall algorithm for all pairs shortest paths
C. Mergesort
D. Hamiltonian circuit

List-II

1. Backtracking
2. Greedy method
3. Dynamic programming
4. Divide and conquer

Codes:

A B C D
(a) 3 2 4 1
(b) 1 2 4 3
(c) 2 3 4 1
(d) 2 1 3 4

Options:

(A): a
(B): b
(C): c
(D): d

Ans: (C)

Q3. [GATE-CS-2017]
Kadane algorithm is generally used to find out.

(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

Ans: (B) Maximum sum subarray present in an array

Q4. [GATE-CS-2017]
Which of the standard algorithms shown below is not based 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

Ans: (A) Prim’s Minimum Spanning Tree

Q5. [GATE-CS-2014]
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 = ___.

(A) 33
(B) 23
(C) 43
(D) 34

Ans: (D) 34

As the GATE Exam 2024 is coming up, having a good grasp of dynamic programming is really important for those looking to tackle tricky computational problems. These notes are here to help you understand the basic principles, strategies, and real-life uses of dynamic programming. They’re like a handy guide to becoming a pro at dynamic programming, making it easier for you to ace the GATE exam. So, get ready to dive into the world of dynamic programming and make problem-solving a breeze!