5.6. Inductive Structure of Edit Distance

Try these first

1. 1.

   Calculate the Edit Distance for 'bat' and 'cat'.

   Hint

   Consider only character replacements.

2. 2.

   What operation is used to convert 'good' to 'goood'?

   Hint

   Think about how we add characters.

3. 3.

   What does Edit Distance measure?

   • Number of characters in a string
   • How alike two strings are
   • Time complexity of an algorithm

   Hint

   Think of the purpose of measuring similarity.

4. 4.

   True or False: Edit Distance can only be calculated for words with the same length.

   • True
   • False

   Hint

   Consider the flexibility of character operations.

5. 5.

   How would you convert 'algorithm' to 'alliteration'? Calculate the required Edit Distance.

   Hint

   Start by identifying shared and differing characters between the two words.

6. 6.

   Given two strings of different lengths, 'happy' and 'unhappiness', calculate the Edit Distance.

   Hint

   Consider how you can minimize the longer string to match the shorter one.