JAMIA 2026 — Computer PYQ

Correct Option: (d) Dynamic Programming

Solution

Understanding Longest Common Subsequence (LCS)

The Longest Common Subsequence problem aims to find the longest subsequence common to all sequences in a given set of sequences (frequently just two strings). Unlike substrings, subsequences are not required to occupy consecutive positions within the original strings.

Why Dynamic Programming (DP)?

The LCS problem exhibits two classic properties that make it perfect for a Dynamic Programming approach:

1. Optimal Substructure: The optimal solution to the main problem contains optimal solutions to its smaller subproblems.

2. Overlapping Subproblems: A recursive solution solves the same subproblems repeatedly rather than generating new ones.

Let two sequences be $X$ of length $m$ and $Y$ of length $n$. We define a matrix $L[i][j]$ to store the length of the LCS of prefixes $X[0\dots i-1]$ and $Y[0\dots j-1]$. The mathematical recurrence relation is modeled using the following piecewise function:

$$L[i][j]=\{\begin{array}{ll}0& amp;\text{if }i=0\text{ or }j=0\\ L[i-1][j-1]+1& amp;\text{if }X[i-1]=Y[j-1]\\ \max (L[i-1][j],L[i][j-1])& amp;\text{if }X[i-1]\ne Y[j-1]\end{array}$$

Step-by-Step Algorithm Complexity

• Using a plain recursive approach (Divide and Conquer) results in an inefficient exponential time complexity of $\mathcal{O}(2^{m+n})$.

• By applying Dynamic Programming (memoization or tabulation), we reduce the time complexity down to a highly efficient polynomial bound:

$$\text{Time Complexity}=\mathcal{O}(m\times n)$$

$$\text{Space Complexity}=\mathcal{O}(m\times n)$$

Once the DP table is completely filled out, we can easily find all longest common subsequences by utilizing a Backtracking procedure starting from cell $L[m][n]$ to trace out every valid optimal path back to $L[0][0]$.

Evaluation of Other Paradigms

• (a) Greedy method: Fails because it makes localized, shortsighted choices at each step without analyzing global constraints, which leads to suboptimal solutions for structural sequence matching.

• (b) Divide and Conquer: Leads to duplicate recursive execution states, leading to an intractable run-time computation step.

• (c) Backtracking: While backtracking is used after computing the DP table to construct the actual strings, relying entirely on raw backtracking from scratch results in exhaustive brute-force search over mutations.

Thus, Dynamic Programming is the core paradigm used to solve and compute the optimal values for the LCS problem.