L20-21 (Memoization, more Dynamic Programming) Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What’s the definition of Memoization

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How is Memoization implemented?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Discuss the pros and cons of memoization

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly