TRB PG Assistant - Design Techniques - divide and conquer, dynamic programming, greedy algorithms, backtracking, branch and bound Online Test (MCQ Quiz)

1. Which design technique involves breaking down a problem into smaller, independent subproblems of the same type, solving them recursively, and then combining their solutions?

A) Greedy Algorithms B) Dynamic Programming C) Divide and Conquer D) Backtracking

2. In the context of Divide and Conquer, what is the primary goal of the 'combine' step?

A) To solve the subproblems B) To merge the solutions of subproblems into a solution for the original problem C) To divide the problem into smaller instances D) To check for base cases

3. Which algorithm design paradigm is characterized by making the locally optimal choice at each stage with the hope of finding a global optimum?

A) Divide and Conquer B) Dynamic Programming C) Greedy Algorithms D) Backtracking

4. Dynamic Programming is most effective when a problem exhibits which two properties?

A) Optimal substructure and overlapping subproblems B) Greedy choice property and optimal substructure C) Divide and conquer and overlapping subproblems D) Brute force and memoization

5. What is the term for storing the results of expensive function calls and returning the cached result when the same inputs occur again, often used in Dynamic Programming?

A) Recursion B) Memoization C) Iteration D) Backtracking

6. Which technique explores all possible solutions by incrementally building candidates and abandoning a candidate ('pruning') as soon as it is determined that it cannot possibly lead to a valid solution?

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Divide and Conquer

7. Which of the following is a classic example of a problem solved efficiently using the Divide and Conquer technique?

A) Traveling Salesperson Problem B) Merge Sort C) Knapsack Problem D) Longest Common Subsequence

8. The algorithm for finding the shortest path in a graph with non-negative edge weights, like Dijkstra's algorithm, is a prime example of which design technique?

A) Dynamic Programming B) Divide and Conquer C) Greedy Algorithms D) Backtracking

9. Which technique is often described as a form of depth-first search in the state space tree?

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Branch and Bound

10. When using Dynamic Programming, building the solution from the smallest subproblems up to the original problem is known as:

A) Top-down approach (Memoization) B) Bottom-up approach (Tabulation) C) Recursive approach D) Greedy approach

11. The problem of finding the minimum number of coins to make a given amount of change is typically solved using which technique?

A) Greedy Algorithms (sometimes incorrect) B) Dynamic Programming C) Divide and Conquer D) Backtracking

12. Which design technique is suitable for problems where the solution can be constructed step-by-step, and at each step, a decision is made that is locally optimal?

A) Divide and Conquer B) Dynamic Programming C) Greedy Algorithms D) Backtracking

13. The 8 Queens puzzle is a classic problem often solved using:

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Divide and Conquer

14. What is the primary difference between memoization and tabulation in Dynamic Programming?

A) Memoization uses recursion, tabulation uses iteration. B) Memoization solves subproblems as needed, tabulation solves all subproblems systematically. C) Memoization stores results in a table, tabulation uses a hash map. D) Memoization is top-down, tabulation is bottom-up.

15. Which of the following algorithms is NOT typically considered a Divide and Conquer algorithm?

A) Quick Sort B) Binary Search C) Heap Sort D) Merge Sort

16. The Fractional Knapsack problem is optimally solved using which technique?

A) Dynamic Programming B) Greedy Algorithms C) Backtracking D) Divide and Conquer

17. Which technique is generally used for optimization problems where the solution space is structured as a tree?

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Branch and Bound

18. What does 'optimal substructure' mean in the context of Dynamic Programming?

A) The problem can be divided into smaller, independent subproblems. B) The optimal solution to the problem contains optimal solutions to its subproblems. C) The same subproblems are solved multiple times. D) The problem can be solved by making a sequence of locally optimal choices.

19. Which technique is suitable for problems that can be modeled as finding a path in a state-space graph, where we want to find a path that satisfies certain constraints?

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Divide and Conquer

20. The problem of finding the Longest Common Subsequence (LCS) is a classic example solved using:

A) Greedy Algorithms B) Dynamic Programming C) Divide and Conquer D) Backtracking

21. In Branch and Bound, what is the purpose of a 'bound'?

A) To explore all possible solutions B) To prune branches of the search tree that cannot lead to an optimal solution C) To divide the problem into smaller subproblems D) To make a locally optimal choice

22. Which algorithm design technique is most appropriate for problems where the optimal solution can be constructed by making a sequence of choices, and each choice must be locally optimal?

A) Dynamic Programming B) Divide and Conquer C) Greedy Algorithms D) Backtracking

23. What is the 'state space tree' in the context of Backtracking?

A) A tree representing the divisions of a problem. B) A tree where each node represents a partial solution and edges represent choices. C) A tree showing the optimal substructure of a problem. D) A tree representing the greedy choices made.

24. The Floyd-Warshall algorithm, which finds all-pairs shortest paths, is an example of which design technique?

A) Greedy Algorithms B) Divide and Conquer C) Dynamic Programming D) Backtracking

25. Which technique is generally less efficient than Dynamic Programming for problems with overlapping subproblems because it recomputes solutions to the same subproblems multiple times?

A) Greedy Algorithms B) Divide and Conquer (without memoization) C) Pure Recursion D) Backtracking

26. The problem of finding the maximum value in the 0/1 Knapsack problem is typically solved using:

A) Greedy Algorithms B) Dynamic Programming C) Divide and Conquer D) Backtracking

27. What is the primary advantage of using a Greedy approach when applicable?

A) Guarantees optimality for all problems. B) Often simpler and more efficient than Dynamic Programming. C) Explores all possible solutions systematically. D) Always finds the globally optimal solution.

28. Which technique involves systematically searching for a solution by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time?

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Divide and Conquer

29. The problem of finding the shortest path in a graph with potentially negative edge weights but no negative cycles, like the Bellman-Ford algorithm, can be related to which design paradigm?

A) Greedy Algorithms B) Divide and Conquer C) Dynamic Programming D) Backtracking

30. What is the 'greedy-choice property'?

A) An optimal solution can be reached by making a sequence of locally optimal choices. B) The problem can be broken down into smaller, independent subproblems. C) The optimal solution contains optimal solutions to subproblems. D) The problem can be solved by exploring all possible paths.

31. Which of the following is an example of a problem solved using Backtracking?

A) Merge Sort B) Dijkstra's Algorithm C) N-Queens Problem D) Fibonacci Sequence Calculation

32. Branch and Bound is particularly useful for solving:

A) Problems with simple recursive structures B) Problems that can be optimally solved with a single greedy choice C) Combinatorial optimization problems D) Problems with overlapping subproblems only

33. What is the main characteristic of 'overlapping subproblems' in Dynamic Programming?

A) The same subproblems are encountered and solved multiple times. B) The solution to a problem depends on the solution to a single larger problem. C) The problem can be divided into many unrelated subproblems. D) The optimal solution is found by making a single best choice.

34. Which Divide and Conquer algorithm sorts an array by recursively dividing the array into two halves, sorting each half, and then merging the two sorted halves?

A) Quick Sort B) Heap Sort C) Merge Sort D) Bubble Sort

35. The problem of finding the shortest path in a graph with non-negative edge weights, using a priority queue to explore nodes, is characteristic of:

A) Dynamic Programming B) Backtracking C) Greedy Algorithms D) Divide and Conquer

36. Which technique is often used to find all permutations or combinations of a set that satisfy certain conditions?

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Divide and Conquer

37. What is the primary goal of the 'divide' step in a Divide and Conquer algorithm?

A) To combine solutions of subproblems B) To solve the base case C) To break the problem into smaller instances of the same problem D) To prune the search space

38. The problem of finding the nth Fibonacci number using recursion without memoization suffers from:

A) Lack of optimal substructure B) Overlapping subproblems C) Greedy choice property violation D) Inability to be divided

39. Which technique is used for optimization problems where the search space can be represented as a tree, and bounding functions are used to eliminate subtrees that cannot contain the optimal solution?

A) Dynamic Programming B) Backtracking C) Greedy Algorithms D) Branch and Bound

40. Consider the problem of making change for a given amount using the minimum number of coins. If the available coin denominations are {1, 3, 4} and the target amount is 6, a greedy approach might pick {4, 1, 1} (3 coins), while the optimal solution is {3, 3} (2 coins). This illustrates:

A) Dynamic Programming is always better than Greedy. B) Greedy algorithms do not always yield optimal solutions. C) Divide and Conquer is suitable here. D) Backtracking is the only correct method.

41. What is the time complexity of the naive recursive calculation of the nth Fibonacci number?

A) O(n) B) O(log n) C) O(n^2) D) O(2^n)

42. Which technique is used in algorithms like Prim's and Kruskal's for finding Minimum Spanning Trees?

A) Dynamic Programming B) Divide and Conquer C) Greedy Algorithms D) Backtracking

43. The problem of finding the shortest path in a Directed Acyclic Graph (DAG) can be efficiently solved using:

A) Greedy Algorithms B) Dynamic Programming C) Backtracking D) Branch and Bound

44. What is a key characteristic of problems suitable for Branch and Bound?

A) They can be solved by making a single locally optimal choice. B) They involve breaking the problem into identical subproblems. C) They are optimization problems with a large search space that can be pruned. D) They have solutions that are built by incremental choices.

45. Which of the following is a common strategy used in Dynamic Programming to avoid recomputing subproblems?

A) Randomized selection B) Memoization or Tabulation C) Divide and conquer D) Greedy choices

46. The process of systematically exploring all potential solutions by building them incrementally and abandoning a partial solution as soon as it's determined that it cannot lead to a valid complete solution is known as:

A) Greedy Search B) Dynamic Programming C) Backtracking D) Divide and Conquer

47. Which design technique is based on the principle that the optimal solution to a problem contains optimal solutions to its subproblems?

A) Greedy Algorithms B) Divide and Conquer C) Dynamic Programming D) Backtracking

48. The algorithm for finding the convex hull of a set of points, such as the Graham scan or Monotone Chain algorithm, often employs which design technique?

A) Greedy Algorithms B) Dynamic Programming C) Divide and Conquer D) Backtracking

49. Which technique is generally preferred for solving the 0/1 Knapsack problem over a greedy approach because the greedy choice property does not hold?

A) Divide and Conquer B) Backtracking C) Dynamic Programming D) Randomized Algorithms

Design Techniques - divide and conquer, dynamic programming, greedy algorithms, backtracking, branch and bound - Online Test

Test Results