# Questions & Answers of Dynamic Programming

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 $0\le i\le n-2$

${L}_{i}=\begin{array}{l}\left\{\begin{array}{ll}1+{L}_{i+1}& ifA\left[i\right]

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 $\le$ i $\le$ n, 0 $\le$ j $\le$ 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 $\le$ i $\le$ n and ai $\le$ j $\le$ 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 $\le$ i $\le$ n, 0 $\le$ j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, ... ai} whose elements sum to j.