Q. In the context of dynamic programming, what does 'memoization' refer to?
A.
Storing results of expensive function calls and reusing them
B.
Sorting data before processing
C.
Using a stack to manage function calls
D.
Creating a binary tree for data storage
Solution
Memoization is a technique used in dynamic programming to store the results of expensive function calls and reuse them when the same inputs occur again.
Correct Answer:
A
— Storing results of expensive function calls and reusing them
Q. What is the primary use of dynamic programming in algorithm design?
A.
To solve problems with overlapping subproblems and optimal substructure
B.
To sort large datasets efficiently
C.
To traverse trees and graphs
D.
To implement data structures like stacks and queues
Solution
Dynamic programming is primarily used to solve problems that can be broken down into overlapping subproblems and have optimal substructure, allowing for efficient computation.
Correct Answer:
A
— To solve problems with overlapping subproblems and optimal substructure
Q. What is the space complexity of the dynamic programming solution for the Longest Increasing Subsequence problem?
A.
O(n)
B.
O(n^2)
C.
O(log n)
D.
O(1)
Solution
The space complexity of the dynamic programming solution for the Longest Increasing Subsequence problem is O(n) due to the storage of intermediate results.
Q. What is the time complexity of the dynamic programming solution for the Fibonacci sequence?
A.
O(n)
B.
O(n^2)
C.
O(2^n)
D.
O(log n)
Solution
The time complexity of the dynamic programming solution for the Fibonacci sequence is O(n) because it computes each Fibonacci number only once and stores the results.
Q. Which dynamic programming problem involves partitioning a set into two subsets with equal sum?
A.
Subset Sum Problem
B.
Longest Common Subsequence
C.
Fibonacci Sequence
D.
Coin Change Problem
Solution
The Subset Sum Problem involves partitioning a set into two subsets such that the sum of elements in both subsets is equal, and it can be solved using dynamic programming.
