1. (100 points) Please implement the algorithm for computing edit distance.

A template python file editdistance_incomplete.py is provided.

You need to fill 7 lines, which are indicated by the comments # Need to add one line here or # Need to complete this line.

You need to copy and paste the outputs of your algorithm in the console/terminal for the following two examples.

Example 1:

sString1 = "kitten"

sString2 = "sitting"

Output in your algorithm:

Example 2:

sString1 = "GAMBOL"

sString2 = "GUMBO"

incomplete skeleton:

def edit_distance(s1, s2): m = len(s1) + 1 n = len(s2) + 1

# Initialize the matrix mTable = {} for i in range(0, m): for j in range(0, n): mTable[i, j] = 0

for i in range(0, m): # Need to add one line here

for j in range(0, n): # Need to add one line here

for i in range(1, m): for j in range(1, n): # Need to add one line here

# Need to add one line here

# Print the edit distance matrix print("Edit Distance Matrix ") print(" ", end='') for j in range(n-1): print("| " + s2[j] + " ", end='') print(" ") for i in range(0, m): if i == 0: print(" ", end='') if i > 0: print(" " + s1[i - 1] + " ", end='') for j in range(0, n): print("| " + str(mTable[i, j]) + " ", end='') print(" ")

return mTable, mTable[m - 1, n - 1]

def get_edits(s1, s2, mTable, nEditDist): m = len(s1) + 1 n = len(s2) + 1

i_old = m - 1 j_old = n - 1 i_new = m - 1 j_new = n - 1 sOperation = "" nIndexOfOperation = nEditDist - 1 sOperationList = {} for i in range(0, nEditDist - 1): sOperationList[i] = "" while 1: nLeft = mTable[i_old, j_old-1] nUp = mTable[i_old-1, j_old] nUpLeft = mTable[i_old-1, j_old-1] if nUpLeft <= nLeft and nUpLeft <= nUp: i_new = i_old - 1 j_new = j_old - 1 if mTable[i_old, j_old] > nUpLeft: sOperation = # Need to complete this line sOperationList[nIndexOfOperation] = sOperation nIndexOfOperation -= 1 elif nLeft <= nUpLeft and nLeft <= nUp: i_new = i_old j_new = j_old - 1 if mTable[i_old, j_old] > nLeft: sOperation = # Need to complete this line sOperationList[nIndexOfOperation] = sOperation nIndexOfOperation -= 1 elif nUp <= nUpLeft and nUp <= nLeft: i_new = i_old - 1 j_new = j_old if mTable[i_old, j_old] > nUp: sOperation = # Need to complete this line sOperationList[nIndexOfOperation] = sOperation nIndexOfOperation -= 1 i_old = i_new j_old = j_new if i_old == 0 and j_old == 0: break

print("the sequence of the edits:") for i in range(0, nEditDist): print("Step " + str(i + 1) + " : " + sOperationList[i])

if __name__ == "__main__": # Example 1 sString1 = "kitten" sString2 = "sitting" # Example 2 # sString1 = "GAMBOL" # sString2 = "GUMBO" mTable, nEditDist = edit_distance(sString1, sString2) print("Edit distance is " + str(nEditDist)) get_edits(sString1, sString2, mTable, nEditDist)