UGC NET - Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound. Online Test (MCQ Quiz)

1. Which design technique is characterized by breaking down a problem into smaller, independent subproblems of the same type?

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

2. In which design technique are solutions to subproblems solved only once and their results stored to avoid recomputation?

A) Divide and Conquer B) Dynamic Programming C) Greedy Algorithm D) Branch and Bound

3. What is the core principle of a Greedy Algorithm?

A) Explore all possible solutions and choose the best. B) Make the locally optimal choice at each step. C) Solve subproblems recursively and combine results. D) Systematically search the solution space.

4. Which technique explores potential solutions by incrementally building a candidate solution and abandoning it if it's determined that it cannot lead to a valid solution?

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

5. Branch and Bound is primarily used for solving which type of problems?

A) Problems with overlapping subproblems B) Optimization problems C) Problems with independent subproblems D) Problems requiring exhaustive search

6. Which of the following algorithms is a classic example of the Divide and Conquer technique?

A) Dijkstra's Algorithm B) Merge Sort C) Prim's Algorithm D) Kruskal's Algorithm

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

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

8. Which design technique is characterized by exploring all possible paths in a state-space tree?

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

9. Consider the problem of finding the minimum number of coins to make a given amount. Which technique is generally NOT suitable for this problem if we want the optimal solution?

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

10. In the context of Branch and Bound, what is a 'bound' used for?

A) To define the state space. B) To prune subtrees that cannot lead to an optimal solution. C) To represent a feasible solution. D) To divide the problem into subproblems.

11. Which design technique is most suitable for problems exhibiting optimal substructure and overlapping subproblems?

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

12. The 8-Queens puzzle is a classic problem solved using which technique?

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

13. When does a greedy approach guarantee an optimal solution?

A) Always B) When the problem exhibits the greedy choice property and optimal substructure. C) When the problem has overlapping subproblems. D) When the problem can be solved recursively.

14. Which technique is generally more efficient than brute-force search for optimization problems, by intelligently exploring the search space?

A) Divide and Conquer B) Greedy Algorithm C) Backtracking D) Branch and Bound

15. What is the primary difference between Backtracking and Branch and Bound?

A) Backtracking explores all solutions, Branch and Bound prunes. B) Backtracking is for optimization, Branch and Bound for feasibility. C) Branch and Bound uses bounds to prune, while Backtracking abandons based on constraints. D) Backtracking is recursive, Branch and Bound is iterative.

16. Which algorithm for finding the shortest path in a graph with non-negative edge weights is a prime example of a greedy algorithm?

A) Bellman-Ford Algorithm B) Floyd-Warshall Algorithm C) Dijkstra's Algorithm D) Breadth-First Search

17. The problem of finding the minimum spanning tree is efficiently solved using which two greedy algorithms?

A) Dijkstra's and Prim's B) Kruskal's and Prim's C) Dijkstra's and Kruskal's D) Huffman Coding and Prim's

18. Which design technique is often used to solve problems where the solution can be constructed step-by-step, and at each step, a decision is made that seems best at that moment?

A) Dynamic Programming B) Divide and Conquer C) Greedy Algorithm D) Branch and Bound

19. When using Dynamic Programming, what is the term for storing the results of subproblems?

A) Recursion B) Memoization or Tabulation C) Backtracking D) Branching

20. Which of the following is a characteristic of problems suitable for Divide and Conquer?

A) Overlapping subproblems B) Optimal substructure C) Independence of subproblems D) Greedy choice property

21. The Traveling Salesperson Problem (TSP) is a classic example of a problem that is NP-hard and often approached using which technique for finding optimal or near-optimal solutions?

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

22. Which technique involves exploring a state-space tree and systematically searching for a solution by trying to build a solution incrementally?

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

23. Consider the problem of finding the longest common subsequence of two strings. Which design technique is most appropriate?

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

24. In Branch and Bound, a 'branch' operation typically involves:

A) Pruning a subtree. B) Generating child nodes from a parent node. C) Calculating a lower bound. D) Finding a feasible solution.

25. Which technique is often described as a refined version of depth-first search that uses bounding functions to avoid searching parts of the state space that cannot yield a better solution than the best one found so far?

A) Dynamic Programming B) Greedy Algorithm C) Divide and Conquer D) Branch and Bound

26. The Huffman coding algorithm, used for data compression, is an example of which design technique?

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

27. Which of the following is a key characteristic of problems suitable for Dynamic Programming?

A) Independent subproblems B) Overlapping subproblems C) Non-optimal substructure D) Greedy choice property only

28. When implementing Divide and Conquer, the combination step is crucial for:

A) Breaking down the problem. B) Solving the subproblems. C) Merging the solutions of subproblems. D) Avoiding recomputation.

29. Which technique is suitable for problems where we need to make a sequence of decisions, and each decision leads to a new state, and we want to find a path from an initial state to a goal state?

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

30. A problem exhibits 'optimal substructure' if:

A) Its optimal solution can be constructed from optimal solutions of its subproblems. B) It has many overlapping subproblems. C) A greedy choice leads to a global optimum. D) The problem can be divided into independent subproblems.

31. Which of the following is a common strategy for Branch and Bound to find the best possible solution?

A) Random exploration B) Depth-first search with pruning C) Breadth-first search with pruning D) Always choosing the first feasible solution found

32. The QuickSort algorithm is a classic example of:

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

33. Which design technique is characterized by making a series of choices that are locally optimal, hoping that these choices will lead to a globally optimal solution?

A) Divide and Conquer B) Dynamic Programming C) Greedy Algorithm D) Branch and Bound

34. Consider the Knapsack problem (0/1). Which design technique is suitable for finding the optimal solution?

A) Greedy Algorithm B) Divide and Conquer C) Dynamic Programming D) Backtracking (without optimization)

35. What is the main advantage of using Dynamic Programming over simple recursion for problems with overlapping subproblems?

A) Reduced time complexity by avoiding recomputation. B) Simpler implementation. C) Guaranteed global optimum. D) Faster exploration of the search space.

36. Which technique involves exploring a solution space by systematically generating candidate solutions and discarding them if they cannot lead to a valid or optimal solution?

A) Divide and Conquer B) Greedy Algorithm C) Backtracking D) Branch and Bound

37. When does a simple recursive approach to a problem often become inefficient?

A) When subproblems are independent. B) When there are overlapping subproblems that are recomputed multiple times. C) When the problem can be solved with a single greedy choice. D) When the problem is easily divided.

38. Which of the following problems is best solved using a Greedy approach?

A) Finding the shortest path in a graph with negative weights. B) The 0/1 Knapsack problem. C) Activity Selection Problem. D) The Traveling Salesperson Problem.

39. In the context of Backtracking, what is a 'partial solution'?

A) A complete and valid solution. B) A solution that has been pruned. C) A candidate solution that is still being built. D) An infeasible solution.

40. The matrix chain multiplication problem is a classic example solved using:

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

41. Which of the following is a key requirement for a problem to be solvable by Divide and Conquer?

A) Overlapping subproblems B) Optimal substructure C) Greedy choice property D) Independent subproblems that can be solved recursively

42. What is the primary goal of the 'bound' in Branch and Bound?

A) To represent a feasible solution. B) To explore the entire state space. C) To estimate the best possible solution in a subtree and prune if it's worse than the current best. D) To divide the problem into smaller parts.

43. Which of these algorithms is NOT typically associated with Divide and Conquer?

A) Merge Sort B) QuickSort C) Binary Search D) Dijkstra's Algorithm

44. Backtracking is often implemented using which programming paradigm?

A) Iterative loops B) Recursion C) Functional programming D) Object-oriented programming

45. The problem of finding the maximum subarray sum can be solved efficiently using which of the following techniques?

A) Greedy Algorithm B) Divide and Conquer C) Dynamic Programming D) Branch and Bound

46. Which design technique focuses on making the best possible choice at each stage, without considering future consequences, in the hope of finding an optimal overall solution?

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

47. In Dynamic Programming, the two main approaches to storing subproblem solutions are:

A) Recursion and Iteration B) Memoization and Tabulation C) Depth-First and Breadth-First Search D) Branching and Bounding

48. Which technique is characterized by exploring possibilities by trying to build a solution incrementally, and if at any point the partial solution cannot be extended to a complete solution, it backtracks?

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

49. Which of the following is a key characteristic of problems suitable for the Greedy approach?

A) Overlapping subproblems B) Optimal substructure and the greedy-choice property C) Need for exhaustive search D) Exploration of a state-space tree

50. The 'state-space tree' is a fundamental concept used in which design techniques?

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

Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound. - Online Test

Test Results