1. Which of the following best describes dynamic programming?
a) A method to solve optimization problems by breaking them down into simpler subproblems
b) A technique to solve linear programming problems
c) A method to solve problems by recursively breaking them down into smaller overlapping subproblems
d) A technique to solve problems by randomly generating solutions
Answer: a) A method to solve optimization problems by breaking them down into simpler subproblems
Explanation: Dynamic programming is a method used to solve optimization problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the solutions to avoid redundant computations.
2. In dynamic programming, what is the main principle behind solving a problem?
a) Recursion
b) Divide and conquer
c) Memoization
d) Randomization
Answer: c) Memoization
Explanation: Memoization involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.
3. Which problem can be efficiently solved using the dynamic programming approach?
a) Sorting
b) Searching
c) Matrix multiplication
d) Hashing
Answer: c) Matrix multiplication
Explanation: Matrix multiplication can be efficiently solved using dynamic programming by breaking down the problem into smaller subproblems and storing the solutions to avoid redundant computations.
4. The 0/1 knapsack problem is an example of which type of problem?
a) Linear programming
b) Integer programming
c) Dynamic programming
d) Heuristic optimization
Answer: c) Dynamic programming
Explanation: The 0/1 knapsack problem is a classic example of a problem that can be efficiently solved using dynamic programming.
5. What does the 0/1 knapsack problem involve?
a) Filling a knapsack to maximize the total value without exceeding its capacity
b) Filling a knapsack with items of varying sizes
c) Filling a knapsack without considering the total value
d) Filling a knapsack with only one type of item
Answer: a) Filling a knapsack to maximize the total value without exceeding its capacity
Explanation: In the 0/1 knapsack problem, items have a weight and a value, and the objective is to select a subset of items to maximize the total value without exceeding the capacity of the knapsack.
6. The Floyd-Warshall algorithm is used for?
a) Finding the shortest path in a weighted graph
b) Sorting elements in an array
c) Balancing a binary search tree
d) Generating random permutations
Answer: a) Finding the shortest path in a weighted graph
Explanation: The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph.
7. Which of the following is NOT a characteristic of dynamic programming?
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy choice
Answer: d) Greedy choice
Explanation: While both dynamic programming and greedy algorithms are techniques used for optimization, greedy algorithms do not necessarily require storing solutions to subproblems.
8. What is the main principle behind the reliability design problem?
a) Maximizing system reliability while minimizing cost
b) Minimizing system reliability while maximizing cost
c) Maximizing system reliability without considering cost
d) Minimizing system reliability without considering cost
Answer: a) Maximizing system reliability while minimizing cost
Explanation: The reliability design problem involves optimizing the reliability of a system while minimizing the associated cost.
9. What does the multistage graph problem involve?
a) Finding the shortest path in a graph with multiple stages
b) Finding the longest path in a graph with multiple stages
c) Optimizing a sequence of decisions in a multistage process
d) Balancing a binary tree
Answer: c) Optimizing a sequence of decisions in a multistage process
Explanation: The multistage graph problem involves making a series of decisions in a multistage process to optimize a certain objective, often solved using dynamic programming.
10. Which technique is essential for efficient implementation of dynamic programming?
a) Recursion
b) Backtracking
c) Greedy approach
d) Memoization
Answer: d) Memoization
Explanation: Memoization, which involves storing solutions to subproblems to avoid redundant computations, is essential for efficient implementation of dynamic programming algorithms.