4.2.3. Algorithmic Approach

Try these first

1. 1.

   What does the edit distance measure?

   Hint

   Think about text transformations.

2. 2.

   What is dynamic programming?

   Hint

   How does it improve efficiency?

3. 3.

   What does edit distance represent?

   • The number of identical characters in two documents.
   • The number of edits to transform one document into another.
   • The length of the longest word.

   Hint

   Focus on what changes are made.

4. 4.

   True or False: Dynamic programming can lead to faster algorithms by avoiding redundant calculations.

   • True
   • False

   Hint

   Consider the benefits of memorization.

5. 5.

   Given the words 'sunday' and 'monday', calculate the edit distance and explain each step.

   Hint

   Consider what character transformations you need to perform.

6. 6.

   Design a small algorithm to compute edit distance using dynamic programming. Explain its time complexity.

   Hint

   Identify how you store previous results in a two-dimensional array.