Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound. - Question Bank
1. The 'state-space tree' is a fundamental concept used in which design techniques?
2. Which of the following is a key characteristic of problems suitable for the Greedy approach?
3. 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?
4. In Dynamic Programming, the two main approaches to storing subproblem solutions are:
5. 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?
6. The problem of finding the maximum subarray sum can be solved efficiently using which of the following techniques?
7. Backtracking is often implemented using which programming paradigm?
8. Which of these algorithms is NOT typically associated with Divide and Conquer?
9. What is the primary goal of the 'bound' in Branch and Bound?
10. Which of the following is a key requirement for a problem to be solvable by Divide and Conquer?
11. The matrix chain multiplication problem is a classic example solved using:
12. In the context of Backtracking, what is a 'partial solution'?
13. Which of the following problems is best solved using a Greedy approach?
14. When does a simple recursive approach to a problem often become inefficient?
15. 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?
16. What is the main advantage of using Dynamic Programming over simple recursion for problems with overlapping subproblems?
17. Consider the Knapsack problem (0/1). Which design technique is suitable for finding the optimal solution?
18. 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?
19. The QuickSort algorithm is a classic example of:
20. Which of the following is a common strategy for Branch and Bound to find the best possible solution?
21. A problem exhibits 'optimal substructure' if:
22. 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?
23. When implementing Divide and Conquer, the combination step is crucial for:
24. Which of the following is a key characteristic of problems suitable for Dynamic Programming?
25. The Huffman coding algorithm, used for data compression, is an example of which design technique?
26. 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?
27. In Branch and Bound, a 'branch' operation typically involves:
28. Consider the problem of finding the longest common subsequence of two strings. Which design technique is most appropriate?
29. Which technique involves exploring a state-space tree and systematically searching for a solution by trying to build a solution incrementally?
30. 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?
31. Which of the following is a characteristic of problems suitable for Divide and Conquer?
32. When using Dynamic Programming, what is the term for storing the results of subproblems?
33. 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?
34. The problem of finding the minimum spanning tree is efficiently solved using which two greedy algorithms?
35. Which algorithm for finding the shortest path in a graph with non-negative edge weights is a prime example of a greedy algorithm?
36. What is the primary difference between Backtracking and Branch and Bound?
37. Which technique is generally more efficient than brute-force search for optimization problems, by intelligently exploring the search space?
38. When does a greedy approach guarantee an optimal solution?
39. The 8-Queens puzzle is a classic problem solved using which technique?
40. Which design technique is most suitable for problems exhibiting optimal substructure and overlapping subproblems?
41. In the context of Branch and Bound, what is a 'bound' used for?
42. 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?
43. Which design technique is characterized by exploring all possible paths in a state-space tree?
44. The Floyd-Warshall algorithm, which finds all-pairs shortest paths, is an example of which design technique?
45. Which of the following algorithms is a classic example of the Divide and Conquer technique?
46. Branch and Bound is primarily used for solving which type of problems?
47. 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?
48. What is the core principle of a Greedy Algorithm?
49. In which design technique are solutions to subproblems solved only once and their results stored to avoid recomputation?
50. Which design technique is characterized by breaking down a problem into smaller, independent subproblems of the same type?