Filling the grid between two strings

Computing · Algorithms & Data Structures · ages 20-21

Name ______________________ Date ____________

Where do you read the final answer?
- The top-left cell
- The far corner cell
- Outside the table
What do the rows and columns of the table stand for?
- Prefixes of each string
- Random numbers
- The alphabet in order
What does walking back through the table give you?
- The alignment that produced the answer
- A new pair of strings
- The time of day
A cell pairs A with U, a mismatch costing 1. What does that choice mean?
- Delete both strings
- Substitute one letter for the other
- Stop the whole table
Turn CAT into CUT with unit costs. Give the edit distance.
Answer: ______________
A delete move skips one character from the side string.
Circle one: True False
Two different tracebacks can give the same corner distance.
Circle one: True False
The corner reads 1 for CAT and CUT, but a friend lists two edits. What is wrong?
- Nothing, corners lie
- CAT and CUT share no letters
- The traceback shows one substitution, so one edit suffices

Answer key

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

The far corner cell · The corner holds the value for the full pair of strings.
Prefixes of each string · Each row steps through one string, each column through the other.
The alignment that produced the answer · The traceback names the actual edits behind the number.
Substitute one letter for the other · Pairing two different last characters is a substitution.
1 · C pairs, T pairs, and one middle substitution makes 1.
True · Each move type skips or pairs exactly as defined.
True · Tied cells offer equal-cost paths to the same answer.
The traceback shows one substitution, so one edit suffices · Pair, swap, pair is a single edit achieving the corner value.