Multiple choice

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 of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(I, j)?

  1. All elements L should be initialized to 0 for the values of l(i, j) to be properly computed.

  2. The values of l(i, j) may be computed in a row major order or column major order of L(M,N).

  3. The values of l(i, j) cannot be computed in either row major order or column major order of L(M,N).

  4. L[p, q] needs to be computed before L[r, s] if either p<r or q<s.

Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Keep practicing — related questions