5.9. Space Complexity

Try these first

1. 1.

   What is edit distance?

   Hint

   Think about the ways we can change one string to become another.

2. 2.

   What are the three operations considered in edit distance?

   Hint

   Consider the changes you can make to each character of a string.

3. 3.

   What is another name for edit distance?

   • Damerau distance
   • Levenshtein distance
   • Hamming distance

   Hint

   Consider notable figures in the field of computer science.

4. 4.

   True or False: Edit distance can only be calculated for words of equal length.

   • True
   • False

   Hint

   Remember how the operations work regardless of string size.

5. 5.

   Given the strings 'algorithm' and 'altruistic', calculate the edit distance and explain your reasoning step-by-step.

   Hint

   Map out the operations clearly to check each transformation.

6. 6.

   Consider a string 'sunday' compared to 'saturday'. Determine the edit distance and provide a clear justification for each step.

   Hint

   Visualize the changes to ensure clarity.