En anglais

Filling the grid between two strings

Computing · Algorithms & Data Structures · ages 20-21

Name ______________________ Date ____________

With unit edit costs, what initializes D(0,3), converting an empty source into a three-character target?
- 0, because the source is empty
- 3, for three insertions
- 1, for inserting the whole word
In a two-string dynamic-programming table, what do the row and column indices describe?
- Prefixes of the two strings
- Positions in a sorted alphabet
- Counts of each distinct letter
At an LCS cell the last characters differ. The value above is 2 and the value to the left is 1. What value is stored?
- 2, keeping the longer result
- 1, keeping the shorter result
- 3, adding the two results
For AB to A, compute D(2,1) with unit costs. Above is 0, left is 2, and diagonal is 1. B and A differ. Which move has minimum cost?
- Insert A, giving cost 3
- Delete B, giving cost 1
- Substitute B, giving cost 2
Convert DOG to DIG. Each insertion, deletion or substitution costs 1. Give the edit distance.
Answer: ______________
When source prefixes index rows, an upward edit-distance traceback move records deletion of one source character.
Circle one: True False
An LCS traceback for RST (rows) and RT (columns) returns RT, with T recorded before R during the backward walk.
Circle one: True False
With unit insertion, deletion and substitution costs, a friend says AB to BA needs one substitution. Which check resolves the claim?
- One substitution changes both character positions
- One insertion changes the order without changing length
- Both positions differ, so two edits are needed

Answer key

For grown-ups. Fold this page away before handing over the rest.

3, for three insertions · Each insertion adds one character and costs 1. Three target characters therefore need three insertions.
Prefixes of the two strings · An index tells how many characters of its string belong to the subproblem. The two indices select two prefixes.
2, keeping the longer result · On a mismatch, LCS takes the maximum of the upper and left values. max(2,1)=2.
Delete B, giving cost 1 · Deletion costs 0+1=1, insertion 2+1=3, and substitution 1+1=2. Deleting B is cheapest.
1 · Replacing O with I costs 1. The strings differ, so cost 0 cannot work. The minimum is 1.
True · An upward move decreases i by one while j stays fixed. It reverses the transition that deleted the last source character.
True · Traceback records T and then R. Reversing gives RT, shared in order by both strings. Its length 2 equals the full target length, so no longer shared subsequence exists.
Both positions differ, so two edits are needed · One substitution fixes only one position. One insertion or deletion changes the length. Two substitutions produce BA, so the distance is 2.