Four matrices M₁, M₂, M₃ and M₄ of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M₁ $$\times$$ M₂) $$\times$$ (M₃ $$\times$$ M₄)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M₁ $$\times$$ M₂) $$\times$$ M₃) $$\times$$ M₄), the total number of scalar multiplications is pqr + prs + pst.

If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:

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 I(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.

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 I(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]

The value 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 of 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₁ ,a₂ ,a₃ ,…,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 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a₁ ,a₂ ,…,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?