CS 371: Edit Distance Module: Edit Distance Dynamic Programming (2 Points)

Module content by Professor Tralie. Module autograder developed by Professor Tralie and Professor Mongan.

Exercise Goals

The goals of this exercise are:
  1. To use memoization/dynamic programming to solve the string edit distance efficiently
Fill in the code to complete the memoization table for string edit distance. When we build such a table from the bottom up, it's referred to as dynamic programming

Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)

Netid
Clicking Run below will check your work and, if it passes, will submit your work automatically. You must be connected to the VPN for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail! VPN access requires Multi-Factor Authentication, which sends you a code when you log into the network. Instructions on configuring these for your account can be found here.

import io, base64 img_str = "" def save_figure_js(): global img_str buf = io.BytesIO() plt.savefig(buf, format='png') buf.seek(0) img_str = "data:image/png;base64,{}".format(base64.b64encode(buf.read()).decode('UTF-8')) audio_sav_arr = [] audio_sav_sr = 44100 def save_audio_js(arr, sr): global audio_sav_arr global audio_sav_sr audio_sav_arr = arr audio_sav_sr = sr

Student Code

import numpy as np def edit(s1, s2): """ Parameters ---------- s1: string of length M A string with M characters s2: string of length N A string with N characters Returns ------- int: The optimal number of add/delete/match/swap operations needed to turn s1 into s2 or vice versa """ M = len(s1) N = len(s2) table = np.zeros((M+1, N+1)) # Fill in the base cases table[0, :] = np.arange(N+1) table[:, 0] = np.arange(M+1) for i in range(1, M+1): for j in range(1, N+1): cost1 = table[i, j-1] + 1 cost2 = 0 # Check table[i-1, j] + 1 cost3 = 0 # Check table[i-1, j-1] (+ 1 if s1[i-1] != s2[j-1]) # Store table[i, j] as the min of the above possibilities return int(table[-1, -1])

Test Code Block

res = "{}.".format(edit("chris", "chase")) res += "{}.".format(edit("school", "fools")) res += "{}".format(edit("topology", "topography")) print(res)

Output