1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

# We wish to find the length of the longest common subsequence (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?

A
expr1 l(i -1, j) + 1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
expr2 max (l(i-1, j - 1), l(i, j))
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
expr1 l(i, j -1)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
expr2 max (l(i-1, j), l(i, j- 1))
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution

## The correct option is D expr2 ≡ max (l(i-1, j), l(i, j- 1))l(i . j) = 0; if either i = 0 or j = 0 = l(i - 1, j - 1); if i, j > 0 and x[i - 1]=Y[j - 1] = max (l(i - 1, j),l(i, j - 1)); if i . j > 0 and x[i - 1] ≠ Y[j - 1] ∴ expr2≡max(l(i−1,j),l(i,j−1))

Suggest Corrections
0
Join BYJU'S Learning Program
Related Videos
Operations on Sets
MATHEMATICS
Watch in App
Explore more
Join BYJU'S Learning Program