L20-21 (Memoization, more Dynamic Programming)

Question 1

What’s the definition of Memoization

Answer 1

• Memoization is a technique used in dynamic programming and other algorithmic approaches to optimize the performance of a function with overlapping subproblems.
• It involves caching and reusing the results of expensive function calls to avoid redundant computations.
• Memoization is particularly useful in recursive algorithms where subproblems are repeatedly solved.

Question 2

How is Memoization implemented?

Answer 2

• Memoization can be implemented using a data structure, such as a hash table or an array, to store the results of function calls.
• This data structure, often called a memo or memoization table, maps input values to their corresponding outputs.
• When a function is called with a specific input, the memoization table is checked for a precomputed result. If the result is found, it is returned immediately; otherwise, the function is executed, and the result is stored in the memoization table for future use.

Question 3

Describe the difference between top-down and bottom-up DP

Answer 3

• Top-down dynamic programming (DP) with memoization involves solving the problem by breaking it into smaller subproblems and solving them recursively.
• Memoization is used to store the results of overlapping subproblems to avoid redundant computations.
• On the other hand, bottom-up DP is an iterative approach that solves the problem by building a solution from smaller subproblems to larger ones.
• While memoization is a characteristic of top-down DP, bottom-up DP does not require memoization as it directly fills the DP table in an organized manner.

Question 4

Discuss the pros and cons of memoization

Answer 4

Pros:
- Reduces time complexity by avoiding redundant computations.
- Can make a significant difference in the performance of recursive algorithms with overlapping subproblems.
- Often easier to implement than a bottom-up DP approach.

Cons:
- Increases space complexity due to the memoization table.
- May introduce the risk of stack overflow in deep recursion scenarios.