A sub-sequence of a given sequence is just the given sequence with some…
PYQ GATE 2009
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]
- A.
expr1 ≡ l(i-1, j) + 1
- B.
expr1 ≡ l(i, j-1)
- C.
expr2 ≡ max(l(i-1, j), l(i, j-1))
- D.
expr2 ≡ max(l(i-1,j-1),l(i,j))
Attempted by 261 students.
Sign up free to check your answer
Sign up freeLoading lesson…