Tutorials
PPTs
Lecture Notes
Objective Questions
Lab ProgramsObjective Type Questions & Answers
Design and Analysis of Algorithms MCQs - Unit-3
1. Which of the following is/are property/properties of a dynamic programming problem?
A . Optimal substructure
B . Overlapping subproblems
C . Greedy approach
D . Both optimal substructure and overlapping subproblems
2. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.
A . Overlapping subproblems
B . Optimal substructure
C . Memoization
D . Greedy
3. If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
A . Overlapping subproblems
B . Optimal substructure
C . Memoization
D . Greedy
4. If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________
A . Dynamic programming
B . Greedy
C . Divide and conquer
D . Recursion
5. In dynamic programming, the technique of storing the previously calculated values is called ___________
A . Saving value property
B . Storing value property
C . Memoization
D . Mapping
6. When a top-down approach of dynamic programming is applied to a problem, it usually _____________
A . Decreases both, the time complexity and the space complexity
B . Decreases the time complexity and increases the space complexity
C . Increases the time complexity and decreases the space complexity
D . Increases both, the time complexity and the space complexity
7. What is the primary goal when constructing an optimal binary search tree?
A . To balance the tree perfectly
B . To minimize the average search time
C . To use all given keys
D . To maximize the tree height
8. What does an optimal binary search tree guarantee?
A . The tree uses the least memory possible.
B . The shortest possible search time for each key.
C . The least number of comparisons in the worst case.
D . 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?
A . dp[i][j] = min(dp[i][k-1] + dp[k+1][j]) + w(i, j)
B . dp[i][j] = dp[i-1][j] + dp[i][j-1]
C . dp[i][j] = sum(dp[i][k-1] * dp[k+1][j]) for all k
D . dp[i][j] = 2 * dp[i-1][j] + dp[i][j-1]
10. Which of the following is necessary to build an optimal binary search tree using dynamic programming?
A . Frequency of access for each key
B . Maximum depth of the tree
C . Binary search algorithm
D . Balanced binary tree
11. How do the costs in the matrix w(i, j) in the optimal binary search tree problem generally behave?
A . Costs decrease as the range increases
B . Costs are constant regardless of the range
C . Costs increase as the range increases
D . No relation between costs and range
12. Which of the following statements is true about the construction of optimal binary search trees?
A . All trees of the same size have the same cost.
B . Only complete binary trees can be optimal.
C . A single tree structure is optimal for any set of keys and frequencies.
D . 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?
A . The sum of the probabilities of accessing keys between i and j
B . The difference between the highest and lowest key values
C . The number of nodes between i and j
D . The depth of the tree between i and j
14. Which dynamic programming solution aspect is most challenging in the context of optimal binary search trees?
A . Computing the weight function w(i, j)
B . Choosing the root for each subtree
C . Implementing the recurrence relation
D . Determining the number of keys
15. What impact does increasing the access probability of a particular key have on its position in an optimal binary search tree?
A . It is more likely to be placed deeper in the tree.
B . It is more likely to be placed at the root.
C . It has no impact on the tree structure.
D . It is more likely to be placed on a leaf.
16. What is the objective of the 0/1 Knapsack Problem?
A . To maximize the total weight of the knapsack.
B . To maximize the total value of the knapsack.
C . To minimize the total weight of the knapsack.
D . To minimize the total value of the knapsack.
17. What does the "0/1" in "0/1 Knapsack Problem" signify?
A . Each item can only be used once.
B . Each item can be divided into smaller parts.
C . Each item is available in unlimited quantities.
D . Each item has no value or weight.
18. Which approach is commonly used to solve the 0/1 Knapsack Problem?
A . Greedy algorithm
B . Dynamic programming
C . Depth-first search
D . Breadth-first search
19. In the dynamic programming solution for the 0/1 Knapsack Problem, what does the function dp[i][w] represent?
A . The maximum value achievable with the first i items and exactly w weight.
B . The maximum weight achievable with the first i items.
C . The minimum weight achievable with the first i items and w value.
D . The minimum value achievable with exactly w weight.
20. What are the constraints of the 0/1 Knapsack Problem?
A . Items` weights and values are negative.
B . Knapsack`s capacity is unlimited.
C . Each item can only be chosen once, and the total weight must not exceed the knapsack`s capacity.
D . Each item can be chosen multiple times.
21. What is the time complexity of the dynamic programming solution for the 0/1 Knapsack Problem?
A . O(n)
B . O(n + W)
C . O(nW)
D . O(W^2)
22. In the context of the 0/1 Knapsack Problem, what is a `feasible solution`?
A . Any solution that does not exceed the knapsack`s capacity.
B . The solution that involves using the least number of items.
C . The solution that maximizes the total weight in the knapsack.
D . The solution that minimizes the total value in the knapsack.
23. What happens when the weight of an item is greater than the current capacity being considered in the dynamic programming table?
A . The item is included in the solution.
B . The item is excluded from the solution.
C . The solution reverts to a previous item.
D . The capacity of the knapsack is increased.
24. What is the primary objective of the All Pairs Shortest Path problem in graph theory?
A . To find the shortest path from one specific vertex to another.
B . To find the shortest path between every pair of vertices in a graph.
C . To detect negative weight cycles in a graph.
D . To find the longest possible path in a graph.
25. Which algorithm is commonly used to solve the APSP problem?
A . Dijkstra’s Algorithm
B . Bellman-Ford Algorithm
C . Floyd-Warshall Algorithm
D . A* Search Algorithm
26. What is the time complexity of the Floyd-Warshall algorithm used for solving the APSP problem?
A . O(V + E)
B . O(V^2)
C . O(VE)
D . 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?
A . The number of edges between vertex i and j.
B . The maximum weight edge in the path from i to j.
C . The shortest path length from vertex i to vertex j.
D . The predecessor vertex to j in the shortest path from i.
28. What is the objective of the Traveling Salesperson Problem (TSP)?
A . To find a shortest possible route that visits every city and returns to the origin city.
B . To maximize the cost of traveling between cities.
C . To visit as many cities as possible.
D . To find the longest possible route that visits every city once.
29. In the dynamic programming solution to the TSP, what does the state dp[mask][i] represent?
A . The shortest path visiting each city in the subset mask exactly once, ending in city i.
B . The number of ways to visit cities in the subset mask.
C . The maximum distance covered by visiting cities in the subset mask.
D . The cost of traveling from the first city in the mask to city i.
Fill in the Blanks
30. Dynamic Programming is a technique used to solve problems by __________ them into overlapping subproblems.
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.
32. ____________ often involves solving each subproblem once and storing the solution to avoid redundant computations.
33. Memoization is a technique in Dynamic Programming where __________ solutions to subproblems are stored and reused when needed.
34. The time complexity of a Dynamic Programming solution is typically determined by the number of __________ and the size of the __________.
35. Dynamic Programming is particularly useful for solving problems like __________, shortest paths, and __________ problems.
36. Dynamic programming can significantly improve the _____________ of solving problems by avoiding redundant calculations.
Relevant Materials :
☞ Design and Analysis of Algorithms MCQs - Unit-1 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-2 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-3 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-4 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-5 - [ DAA ]
Similar Materials :
☞ R - Programming MCQs - Unit-1 - [ R-Programming ]
☞ R - Programming MCQs - Unit-2 - [ R-Programming ]
☞ R - Programming MCQs - Unit-3 - [ R-Programming ]
☞ R - Programming MCQs - Unit-4 - [ R-Programming ]
☞ R - Programming MCQs - Unit-5 - [ R-Programming ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-1 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-2 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-3 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-4 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-5 - [ FLAT ]
☞ PPS MCQs - Unit-1 - [ PPS ]
☞ PPS MCQs - Unit-2 - [ PPS ]
☞ PPS MCQs - Unit-3 - [ PPS ]
☞ PPS MCQs - Unit-4 - [ PPS ]
☞ PPS MCQs - Unit-5 - [ PPS ]
☞ Object Oriented Programming through Java MCQs - Unit-1 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-2 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-3 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-4 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-5 - [ OOP_JAVA ]
☞ Software Engineering MCQs - Unit-1 - [ SE ]
☞ Software Engineering MCQs - Unit-2 - [ SE ]
☞ Software Engineering MCQs - Unit-3 - [ SE ]
☞ Software Engineering MCQs - Unit-4 - [ SE ]
☞ Software Engineering MCQs - Unit-5 - [ SE ]
☞ Data Mining MCQs - Unit-1 - [ DM ]
☞ Data Mining MCQs - Unit-2 - [ DM ]
☞ Data Mining MCQs - Unit-3 - [ DM ]
☞ Data Mining MCQs - Unit-4 - [ DM ]
☞ Data Mining MCQs - Unit-5 - [ DM ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-1 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-2 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-3 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-4 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-5 - [ COA ]
☞ Data Structures Objective Type Question Bank-Unit-1 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-2 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-3 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-4 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-5 - [ DS ]
☞ Database Management System Objective Type Question Bank-Unit-1 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-2 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-3 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-4 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-5 - [ DBMS ]
☞ Cyber Forensics Objective Type Question Bank-Part-2 - [ Cyber Forensics ]
☞ Cyber Forensics Objective Type Question Bank-Part-1 - [ Cyber Forensics ]
☞ Java Programming Objective Type Question Bank - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-1 - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-2 - [ Java Programming ]