Introduction to Programming

Assignment 8

Date: Mon, 22 November 2004

Due on: Fri, 03 December 2004

Memoization (Edit Distance)

You are given a pair of strings s and t. The aim is to edit s to make it equal to t. A single edit step consists of one of the following:

1. Insert a letter in s.
2. Delete a letter from s.
3. Modify a letter in s.

For instance, if s is "rate" and t is "tact", one possible sequence of edit steps is the following:

    (rate,tact) -> (rat,tact)   : delete e 
                -> (ract,tact)  : insert c
                -> (tact,tact)  : modify r to t
    

In this case, it took 3 steps. The edit distance of s and t is the length of the shortest sequence of steps required to transform s into t.

Write a Haskell function

      editdistance :: String -> String -> Int
    

that computes the edit distance of its inputs using memoization. You can use the naive Memo module provided below. An example of how to use this module to compute the length of the least common subsequence is also provided.

• Memo.hs
• lcs-memo.hs