Quiz 5 (Solutions)

CS F364: Design & Analysis of Algorithms

Quiz 5 — June 12, 2026

Coverage: Lectures 1–14

Note

Instructions:

• Time: 15 minutes.
• Write your answers clearly on paper, scan, and upload to Google Classroom.
• Show all steps for full credit.

---

Question: LCS — Dynamic Programming

Let \(c[i, j]\) be the length of the LCS of prefixes \(X[1..i]\) and \(Y[1..j]\).

For strings \(X = \texttt{ABCD}\) and \(Y = \texttt{AXCD}\):

(a) [2 marks] Write the complete recurrence relation for \(c[i, j]\) for all \(i, j > 0\). Clearly state the base case and both cases (\(x_i = y_j\) and \(x_i \neq y_j\)).

(b) [2 marks] Fill in the DP table below. The first row (\(i = 0\)) and first column (\(j = 0\)) are already given.

(c) [1 mark] What is the length of the LCS? What is the actual LCS sequence?

---

Solution

Part (a) — Recurrence Relation

Base case: For \(i = 0\) or \(j = 0\), \(c[i, j] = 0\).

Recurrence: For \(i, j > 0\):

\[ c[i, j] = \begin{cases} c[i-1, j-1] + 1 & \text{if } x_i = y_j \\[4pt] \max(c[i-1, j],\; c[i, j-1]) & \text{if } x_i \neq y_j \end{cases} \]

---

Part (b) — Completed DP Table

\(c[i,j]\)	\(j=0\)	\(j=1\)	\(j=2\)	\(j=3\)	\(j=4\)
	\(\emptyset\)	A	X	C	D
\(i=0\) \(\emptyset\)	0	0	0	0	0
\(i=1\) A	0	1	1	1	1
\(i=2\) B	0	1	1	1	1
\(i=3\) C	0	1	1	2	2
\(i=4\) D	0	1	1	2	3

Computation walkthrough:

• Row 1 (A): \(x_1 = A\), compare with \(y_j\):
  • \(j=1\) (A): \(A = A \Rightarrow c[1,1] = c[0,0] + 1 = 1\)
  • \(j=2\) (X): \(A \neq X \Rightarrow c[1,2] = \max(c[0,2], c[1,1]) = \max(0, 1) = 1\)
  • \(j=3\) (C): \(A \neq C \Rightarrow c[1,3] = \max(c[0,3], c[1,2]) = \max(0, 1) = 1\)
  • \(j=4\) (D): \(A \neq D \Rightarrow c[1,4] = \max(c[0,4], c[1,3]) = \max(0, 1) = 1\)
• Row 2 (B): \(x_2 = B\), all \(y_j\) are A, X, C, D — none match B:
  • \(c[2,j] = \max(c[1,j], c[2,j-1])\) — all cells = 1
• Row 3 (C): \(x_3 = C\), matches \(y_3 = C\):
  • \(j=1\) (A): \(C \neq A \Rightarrow c[3,1] = \max(c[2,1], c[3,0]) = \max(1, 0) = 1\)
  • \(j=2\) (X): \(C \neq X \Rightarrow c[3,2] = \max(c[2,2], c[3,1]) = \max(1, 1) = 1\)
  • \(j=3\) (C): \(C = C \Rightarrow c[3,3] = c[2,2] + 1 = 1 + 1 = 2\)
  • \(j=4\) (D): \(C \neq D \Rightarrow c[3,4] = \max(c[2,4], c[3,3]) = \max(1, 2) = 2\)
• Row 4 (D): \(x_4 = D\), matches \(y_4 = D\):
  • \(j=1\) (A): \(D \neq A \Rightarrow c[4,1] = \max(c[3,1], c[4,0]) = \max(1, 0) = 1\)
  • \(j=2\) (X): \(D \neq X \Rightarrow c[4,2] = \max(c[3,2], c[4,1]) = \max(1, 1) = 1\)
  • \(j=3\) (C): \(D \neq C \Rightarrow c[4,3] = \max(c[3,3], c[4,2]) = \max(2, 1) = 2\)
  • \(j=4\) (D): \(D = D \Rightarrow c[4,4] = c[3,3] + 1 = 2 + 1 = 3\)

---

Part (c) — LCS

LCS length: \(c[4,4] = 3\)

LCS sequence: \(\texttt{ACD}\)

(Traceback: \(c[4,4]\) came from \(c[3,3] + 1\) where \(D = D\); \(c[3,3]\) came from \(c[2,2] + 1\) where \(C = C\); \(c[2,2]\) came from \(c[1,1]\) (max); \(c[1,1]\) came from \(c[0,0] + 1\) where \(A = A\). Reading the matched characters in reverse: D, C, A \(\rightarrow\) “ACD”.)