GATE Questions & Answers of Dynamic programming

What is the Weightage of Dynamic programming in GATE Exam?

Total 8 Questions have been asked from Dynamic programming topic of Algorithms subject in previous GATE papers. Average marks 1.75.

Assume that multiplying a matrix $\style{font-family:'Times New Roman'}{G_1}$ of dimension $\style{font-family:'Times New Roman'}{p\times q}$ with another matrix $\style{font-family:'Times New Roman'}{G_2}$ of dimension $\style{font-family:'Times New Roman'}{q\times r}$ requires pqr scalar multiplications. Computing the product of n matrices $\style{font-family:'Times New Roman'}{G_\mathit1G_\mathit2G_\mathit3\mathit.\mathit.\mathit.G_\mathit n}$ can be done by parenthesizing in different ways. Define $\style{font-family:'Times New Roman'}{G_\mathit i\mathit\;G_{\mathit i\mathit+\mathit1}}$ as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain $\style{font-family:'Times New Roman'}{G_\mathit1G_\mathit2G_\mathit3G_\mathit4G_\mathit5G_\mathit6}$ using parenthesization $\left(G_\mathit1\left(G_\mathit2G_\mathit3\right)\right)\left(G_\mathit4\left(G_\mathit5G_\mathit6\right)\right)\mathit,G_\mathit2G_\mathit3\mathit\;$ and $ G_\mathit5G_\mathit6 $ are the only explicitly computed pairs.

Consider a matrix multiplication chain $\style{font-family:'Times New Roman'}{F_1F_2F_3F_4F_5,}$ where matrices $ F_1,F_2,F_3,F_4 $ and $ F_5 $ are of dimensions $ 2\times25,\;25\times3,\;3\times16,\;16\times1 $, and $ 1\times1000,$ respectively. In the parenthesization of $\style{font-family:'Times New Roman'}{F_1F_2F_3F_4F_5}$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Match the following:

(P) Prim’s algorithm for minimum spanning tree (i) Backtracking
(Q) Floyd – Warshal algorithm for all pairs shortest paths (ii) Greedy method
(R) Mergesort (iii) Dynamic programming
(S) Hamiltonian circuit (iv) Divide and conquer

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 = ___.

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n- 1] is given below.

Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array.

Initialize Ln-1 =1.

For all i such that 0in-2

Li=1+Li+1ifA[i]<A[i+1]1otherwise

Finally the length of the longest monotonically increasing sequence is Max (L0, L1,…….Ln-1).

Which of the following statements is TRUE?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:

l(i,j) = 0,     if either i=0 or j=0
       = expr1, if i,j>0 and
X[i - 1] = Y[j - 1]
       = expr2, if i,j>0 and
X[i - 1] ≠ Y[j - 1]

Which one of the following options is correct?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m + 1 and N = n + 1, such that L[i,j] =l(i,j).

Which one the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, ..., an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X[i, j], 1 i n, 0 j W, is TRUE if and only if there is a subset of {a1, a2, ... ai} whose elements sum to j.

Which of the following is valid for 2 i n and ai j W?

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, ..., an}, and positive integer W, is there a subset of S whose elements sum to W ? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X[i, j], 1 i n, 0 j W, is TRUE if and only if there is a subset of {a1, a2, ... ai} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?