Quiz 5
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[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 | ||||
| \(i=2\) B | 0 | ||||
| \(i=3\) C | 0 | ||||
| \(i=4\) D | 0 |
(c) [1 mark] What is the length of the LCS? What is the actual LCS sequence?