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.

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?

  1. expr1 = l (i − 1, j) + 1

  2. expr1 = l (i, j − 1)

  3. expr2 = max (l (i − 1, j), l (i,j - 1))

  4. expr2 = max (l (i − 1, j − 1), l (i, j))
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Keep practicing — related questions