5.7. Pseudo Code for Edit Distance

Try these first

1. 1.

   What is Edit Distance?

   Hint

   How many operations do we use?

2. 2.

   List the three types of edit operations.

   Hint

   Think about how you would change one word to another.

3. 3.

   What three operations are considered in Edit Distance?

   • Insertion
   • Deletion
   • Substitution
   • Only Deletion
   • Only Insertion

   Hint

   Think about what changes you would make to a string.

4. 4.

   True or False: Edit Distance can be used in spell check applications.

   • True
   • False

   Hint

   Consider how spelling errors get corrected.

5. 5.

   Given the words 'dint' and 'hint', calculate the Edit Distance and detail the operations used.

   Hint

   Look at how one letter differs.

6. 6.

   Design your own algorithm or pseudo-code for calculating Edit Distance while using effective memory management principles.

   Hint

   Think back to how we optimized in class.