Given two sequences 𝑋 and 𝑌: 𝑋 = ⟨𝑎,𝑏,𝑐,𝑏,𝑑,𝑎,𝑏⟩ 𝑌 =…

Solution: The longest common subsequence is ⟨𝑏,𝑐,𝑏,𝑎⟩ (length 4).

• Matching indices in X = ⟨a, b, c, b, d, a, b⟩: positions 2(b), 3(c), 4(b), 6(a).

• Matching indices in Y = ⟨b, d, c, a, b, a⟩: positions 1(b), 3(c), 5(b), 6(a).

• This gives the common subsequence ⟨𝑏,𝑐,𝑏,𝑎⟩ in both sequences.

Why it is longest:

• Other candidate subsequences such as ⟨𝑏,𝑐,𝑎⟩ or ⟨𝑐,𝑎,𝑏⟩ have length 3 and can be extended to ⟨𝑏,𝑐,𝑏,𝑎⟩, so they are not maximal.

• Sequences that try to include two 'a' characters in order (for example ⟨𝑏,𝑐,𝑎,𝑎⟩) fail because X does not have the required two 'a' occurrences after the chosen b and c in the correct order.

• Therefore no common subsequence of length 5 exists, and ⟨𝑏,𝑐,𝑏,𝑎⟩ (length 4) is a longest common subsequence.