2.3.2. Efficiency of Memoization

Try these first

1. 1.

   What does memoization do?

   Hint

   Think about how we can save time in repeated calculations.

2. 2.

   How many paths are there to (1,0) in a 2x1 grid?

   Hint

   You can only go directly down.

3. 3.

   What is the primary advantage of memoization?

   • It optimizes recursive calculations.
   • It complicates recursive functions.
   • It generates new pathfinding algorithms.

   Hint

   Consider what happens when you need a result that has already been computed.

4. 4.

   True or False? Dynamic programming computes all possible solutions before storing results.

   • True
   • False

   Hint

   Think about how dynamic programming builds solutions from smaller parts.

5. 5.

   Determine the total number of paths in an 8x8 grid that has holes at (3,3) and (6,2). Use dynamic programming principles.

   Hint

   Build your table row by row; how do you handle the holes?

6. 6.

   Construct a comparison chart of memoization versus dynamic programming detailing time complexity, situation applicability, and efficiency. Provide examples for each.

   Hint

   Consider the advantages of structure vs. the recursive approach.