4.3.2. Dynamic Programming

Try these first

1. 1.

   What is edit distance?

   Hint

   Think about the types of character operations.

2. 2.

   What does dynamic programming aim to solve?

   Hint

   Consider redundant calculations.

3. 3.

   What technique is often used to calculate the minimum edit distance?

   • Recursion
   • Dynamic Programming
   • Brute Force

   Hint

   Which method is more efficient?

4. 4.

   True or False: Edit distance is only applicable for comparing text documents.

   • True
   • False

   Hint

   Consider applications in coding as well.

5. 5.

   Consider two strings: 'care' and 'cart'. Calculate the edit distance and explain each step.

   Hint

   Think about character operations compared.

6. 6.

   You are given a sequence of steps to transform one string into another. Create a dynamic programming table to show these transformations.

   Hint

   Draw the table for operations and compare strings.