1
Which of the following is/are property/properties of a dynamic programming problem?
Correct Answer
Both optimal substructure and overlapping subproblems
☑ MCQ PRACTICE
Design and Analysis of Algorithms Unit 3
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Design and Analysis of Algorithms - Unit-3
2
If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.
Correct Answer
Optimal substructure
3
If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
Correct Answer
Overlapping subproblems
4
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________
Correct Answer
Divide and conquer
5
In dynamic programming, the technique of storing the previously calculated values is called ___________
Correct Answer
Memoization
6
When a top-down approach of dynamic programming is applied to a problem, it usually _____________
Correct Answer
Decreases the time complexity and increases the space complexity
7
What is the primary goal when constructing an optimal binary search tree?
Correct Answer
To minimize the average search time
8
What does an optimal binary search tree guarantee?
Correct Answer
The minimal cost of searches, weighted by the probabilities of access.
9
What is the recurrence relation used in the dynamic programming solution of optimal binary search trees?
Correct Answer
dp[i][j] = min(dp[i][k-1] + dp[k+1][j]) + w(i, j)
10
Which of the following is necessary to build an optimal binary search tree using dynamic programming?
Correct Answer
Frequency of access for each key
11
How do the costs in the matrix w(i, j) in the optimal binary search tree problem generally behave?
Correct Answer
Costs increase as the range increases
12
Which of the following statements is true about the construction of optimal binary search trees?
Correct Answer
Different key distributions can lead to different optimal trees.
13
What does the weight function w(i, j) represent in the context of optimal binary search trees?
Correct Answer
The sum of the probabilities of accessing keys between i and j
14
Which dynamic programming solution aspect is most challenging in the context of optimal binary search trees?
Correct Answer
Choosing the root for each subtree
15
What impact does increasing the access probability of a particular key have on its position in an optimal binary search tree?
Correct Answer
It is more likely to be placed at the root.
16
What is the objective of the 0/1 Knapsack Problem?
Correct Answer
To maximize the total value of the knapsack.
17
What does the "0/1" in "0/1 Knapsack Problem" signify?
Correct Answer
Each item can only be used once.
18
Which approach is commonly used to solve the 0/1 Knapsack Problem?
Correct Answer
Dynamic programming
19
In the dynamic programming solution for the 0/1 Knapsack Problem, what does the function dp[i][w] represent?
Correct Answer
The maximum value achievable with the first i items and exactly w weight.
20
What are the constraints of the 0/1 Knapsack Problem?
Correct Answer
Each item can only be chosen once, and the total weight must not exceed the knapsack's capacity.
21
What is the time complexity of the dynamic programming solution for the 0/1 Knapsack Problem?
Correct Answer
O(nW)
22
In the context of the 0/1 Knapsack Problem, what is a 'feasible solution'?
Correct Answer
Any solution that does not exceed the knapsack's capacity.
23
What happens when the weight of an item is greater than the current capacity being considered in the dynamic programming table?
Correct Answer
The item is excluded from the solution.
24
What is the primary objective of the All Pairs Shortest Path problem in graph theory?
Correct Answer
To find the shortest path between every pair of vertices in a graph.
25
Which algorithm is commonly used to solve the APSP problem?
Correct Answer
Floyd-Warshall Algorithm
26
What is the time complexity of the Floyd-Warshall algorithm used for solving the APSP problem?
Correct Answer
O(V^3)
27
In the context of the APSP, what does the matrix entry d[i][j] represent after running the Floyd-Warshall algorithm?
Correct Answer
The shortest path length from vertex i to vertex j.
28
What is the objective of the Traveling Salesperson Problem (TSP)?
Correct Answer
To find a shortest possible route that visits every city and returns to the origin city.
29
In the dynamic programming solution to the TSP, what does the state dp[mask][i] represent?
Correct Answer
The shortest path visiting each city in the subset mask exactly once, ending in city i.
Fill in the Blanks
30
Dynamic Programming is a technique used to solve problems by __________ them into overlapping subproblems.
Correct Answer
Breaking down (or decomposing)
31
One key requirement for applying Dynamic Programming is that the problem should exhibit __________, meaning that the solution to a subproblem can be used to solve larger instances of the problem.
Correct Answer
Optimal substructure
32
____________ often involves solving each subproblem once and storing the solution to avoid redundant computations.
Correct Answer
Dynamic Programming
33
Memoization is a technique in Dynamic Programming where __________ solutions to subproblems are stored and reused when needed.
Correct Answer
Intermediate
34
The time complexity of a Dynamic Programming solution is typically determined by the number of __________ and the size of the __________.
Correct Answer
Subproblems, table (or memoization structure)
35
Dynamic Programming is particularly useful for solving problems like __________, shortest paths, and __________ problems.
Correct Answer
Knapsack, scheduling
36
Dynamic programming can significantly improve the _____________ of solving problems by avoiding redundant calculations.
Correct Answer
Efficiency