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