4.3. Recursive Solutions and Their Limitations

Try these first

1. 1.

   What is edit distance?

   Hint

   Think about character changes.

2. 2.

   Name one application of document similarity.

   Hint

   Consider academic settings.

3. 3.

   What is the primary purpose of calculating edit distance?

   • To improve search engines
   • To find do document similarity
   • To detect errors in programming

   Hint

   Consider the context of documents.

4. 4.

   True or False: Recursion can sometimes lead to computing the same values multiple times.

   • True
   • False

   Hint

   Think about how recursion unfolds.

5. 5.

   Calculate the edit distance between the strings "sunday" and "saturday".

   Hint

   Think about each character and what changes are needed.

6. 6.

   Can you devise a dynamic programming solution to compute Fibonacci numbers up to n?

   Hint

   Focus on building the solution incrementally.