Match the following:
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 L_{i} denote the length of the longest monotonically increasing sequence starting at index i in the array.
Initialize L_{n-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]<A[i+1]\\ 1& otherwise\end{array}\right.\end{array}$
Finally the length of the longest monotonically increasing sequence is Max (L_{0}, L_{1},…….L_{n-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?
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 = {a_{1}, a_{2}, a_{3}, ..., a_{n}}, 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 {a_{1}, a_{2}, ... a_{i}} whose elements sum to j.
Which of the following is valid for 2 $\le $ i $\le $ n and a_{i} $\le $ j $\le $ W?
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a_{1}, a_{2}, a_{3}, ..., a_{n}}, 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 {a_{1}, a_{2}, ... a_{i}} whose elements sum to j.
Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?