Official PYQ · 2009Q53Algorithm Design: Dynamic ProgrammingMCQ1 mark

GATE CS 2009 Q53 — Algorithm Design: Dynamic Programming

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?

View worked solution

Answer: C

The function $l(i, j)$ represents the length of the Longest Common Subsequence (LCS) of the prefixes $X[0 \dots i-1]$ and $Y[0 \dots j-1]$ .

We can formulate the recurrence relation by analyzing the last characters of the prefixes, namely $X[i-1]$ and $Y[j-1]$ :

Case 1: The last characters match ( $X[i-1] = Y[j-1]$ )
Since the characters match, they must be part of the LCS. Thus, the length of the LCS increases by $1$ , and we recursively find the LCS of the remaining prefixes of lengths $i-1$ and $j-1$ :
$\text{expr1} = l(i-1, j-1) + 1$
Case 2: The last characters do not match ( $X[i-1] \neq Y[j-1]$ )
Since the characters do not match, both cannot simultaneously be part of the LCS. The optimal solution is the maximum of two possibilities:
- Excluding $X[i-1]$ : $l(i-1, j)$
- Excluding $Y[j-1]$ : $l(i, j-1)$
Thus, the recurrence is:
$\text{expr2} = \max\left(l(i-1, j), l(i, j-1)\right)$

Comparing these with the given options:

Option A is incorrect because $\text{expr1}$ should be $l(i-1, j-1) + 1$ .
Option B is incorrect.
Option C correctly matches our formulation for $\text{expr2}$ .
Option D is incorrect.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Algorithm Design: Dynamic Programming questions

GATE CS 2009 Q53 — Algorithm Design: Dynamic Programming

Related questions