4.2.1. Edit Distance

Try these first

1. 1.

   What is an edit operation?

   Hint

   Think about basic operations like adding or removing letters.

2. 2.

   List the three main types of edit operations.

   Hint

   Recall the concepts we've discussed.

3. 3.

   What does edit distance measure?

   • The length of two documents
   • The number of edits to convert one document to another
   • The number of words in a document

   Hint

   Think about the operations we've covered.

4. 4.

   True or False: A higher edit distance indicates greater similarity between two documents.

   • True
   • False

   Hint

   Recall what edit distance represents.

5. 5.

   Implement an algorithm to calculate the edit distance between two given strings. Optimize it using dynamic programming, then test your algorithm on several string pairs.

   Hint

   Use the logic you've learned for the recursive version.

6. 6.

   You want to help design a plagiarism detection tool. Discuss how you would integrate edit distance into this software while allowing for some degree of permissible editing.

   Hint

   Think about examples where minor edits might legitimize differences.