24.3. End of Lecture

Try these first

1. 1.

   Define memoization in your own words.

   Hint

   Think about how caching works.

2. 2.

   What is the base case for Fibonacci(0) and Fibonacci(1)?

   Hint

   Consider the initial conditions of the Fibonacci sequence.

3. 3.

   What does memoization primarily do?

   • Attempts to minimize function calls
   • Stores results of previous computations
   • Eliminates all recursive calls

   Hint

   Think about caching in computer science.

4. 4.

   Dynamic programming builds a solution by iterating through subproblems. True or False?

   • True
   • False

   Hint

   Consider the implementation approach.

5. 5.

   Develop a dynamic programming solution for calculating the nth Fibonacci number without recursion.

   Hint

   Focus on iterating through the Fibonacci sequence.

6. 6.

   Analyze the time complexity of a purely recursive Fibonacci function versus a memoized version.

   Hint

   Consider the recursive tree structure for purely recursive functions.