5.8. Complexity Analysis

Try these first

1. 1.

   Define Edit Distance in your own words.

   Hint

   Think about the operations involved.

2. 2.

   List the three primary edit operations.

   Hint

   Consider how you can alter a string.

3. 3.

   What does Edit Distance measure?

   • How similar two strings are
   • How long two strings are
   • How many words are in a text

   Hint

   Focus on the purpose of the metric.

4. 4.

   True or False: The Edit Distance can only be calculated for strings of equal length.

   • True
   • False

   Hint

   Think about how characters can be added or removed.

5. 5.

   Given the words 'abcdef' and 'azced', calculate the Edit Distance and describe each step.

   Hint

   Break down the steps and visualize the transformations.

6. 6.

   Create a scenario where Edit Distance can help in finding similarities in two historical texts.

   Hint

   Consider the applications in text analysis.