Questions & Answers of Dynamic Programming

Question No. 13

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

Question No. 147

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

Question No. 25

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?

Question No. 53

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?

Question No. 54

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)?

Question No. 80

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?

Question No. 81

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?