I'm having trouble understanding how this table is constructed. A little before this point in the lecture, we get to take a look at this table. enter image description here

However, he explains the table by basically trying to match each and every character to the end... which makes sense for the bottom two columns that he explained. I then developed a mental model for what he was doing, but I'm wrong - the mental model I made only recreates the rows the professor shows. The others, I can't figure out how to derive!

When I try to go higher in the table, I get different, seemingly useless numbers. Could someone explain the process of a row or two higher, so maybe I can figure out how this works? This is a really cool idea...

1 Answer 1


Oddly, this chart is exactly the opposite of the one used in similarities/more, mirrored horizontally and vertically. Other than that, no difference. You could start at either end of the string, the algorithm doesn't care as long as you're consistent.

Each cell represents a transformation from one string into another. The cell in the lower right represents the transformation ''->'' (empty string into empty string), and therefore has a cost of zero, is the base case. Each row above means one more letter of the source string, each column to the left means one more letter of the destination string. (I'm just assuming they are charted the same way as in similarities/more, but again it doesn't really matter)

Then the cell above represents 'A'->'', and it can be derived from exactly one neighbouring cell, the ''->'' cell. All cells of the last column have only one possible predecessor, the cell below them.

Seems like here the cost for moving horizontally or vertically is 2, while moving diagonally costs 1 if letter doesn't match (and 0 if it does, as there's no change required).

The cell to the left represents ''->'C', which again can only have one predecessor, the cell to the right.

Now all the other cells that are not in the last column or last row have three potential predecessors. The cell representing 'A'->'C' can be derived from the one to the right 'A'->'', the one below ''->'C', or the one diagonally below ''->''. We always pick the one with the lowest total cost, writing down the cost and which way we got there. If two are equal, both represent valid paths of lowest cost, in this case we can pick any.

The cell with the red 3-> for example represents 'CA'->'ACC' (or maybe 'AC'->'CCA' if you want to read it that way), and can be derived from its neighbours 'A'->'ACC' (below), 'CA'->'CC' (right), 'A'->'CC' (below right), which come with costs of 4+2=6, 1+2=3, 3+1=4 associated. Right with 3 has lowest cost, hence the arrow pointing there.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .