Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound. - One Line Questions

1. In the context of Backtracking, what is a 'partial solution'? — A candidate solution that is still being built.
2. When does a greedy approach guarantee an optimal solution? — When the problem exhibits the greedy choice property and optimal substructure.
3. What is the primary difference between Backtracking and Branch and Bound? — Branch and Bound uses bounds to prune, while Backtracking abandons based on constraints.
4. Which algorithm for finding the shortest path in a graph with non-negative edge weights is a prime example of a greedy algorithm? — Dijkstra's Algorithm
5. When implementing Divide and Conquer, the combination step is crucial for: — Merging the solutions of subproblems.
6. Which of the following algorithms is a classic example of the Divide and Conquer technique? — Merge Sort
7. The problem of finding the minimum spanning tree is efficiently solved using which two greedy algorithms? — Kruskal's and Prim's
8. In which design technique are solutions to subproblems solved only once and their results stored to avoid recomputation? — Dynamic Programming
9. 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? — Backtracking
10. The 8-Queens puzzle is a classic problem solved using which technique? — Backtracking
11. Which technique is generally more efficient than brute-force search for optimization problems, by intelligently exploring the search space? — Branch and Bound
12. Which technique involves exploring a state-space tree and systematically searching for a solution by trying to build a solution incrementally? — Backtracking
13. 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? — Backtracking
14. 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? — Greedy Algorithm
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? — Backtracking
16. 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? — Backtracking
17. The 'state-space tree' is a fundamental concept used in which design techniques? — Backtracking and Branch and Bound
18. Which design technique is characterized by breaking down a problem into smaller, independent subproblems of the same type? — Divide and Conquer
19. Which design technique is characterized by exploring all possible paths in a state-space tree? — Backtracking
20. 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? — Greedy Algorithm
21. 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? — Greedy Algorithm
22. 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? — Branch and Bound
23. 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? — Branch and Bound
24. The Huffman coding algorithm, used for data compression, is an example of which design technique? — Greedy Algorithm
25. The QuickSort algorithm is a classic example of: — Divide and Conquer
26. 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? — Greedy Algorithm
27. What is the core principle of a Greedy Algorithm? — Make the locally optimal choice at each step.
28. Which of the following problems is best solved using a Greedy approach? — Activity Selection Problem.
29. The Floyd-Warshall algorithm, which finds all-pairs shortest paths, is an example of which design technique? — Dynamic Programming
30. Which design technique is most suitable for problems exhibiting optimal substructure and overlapping subproblems? — Dynamic Programming
31. Consider the problem of finding the longest common subsequence of two strings. Which design technique is most appropriate? — Dynamic Programming
32. Consider the Knapsack problem (0/1). Which design technique is suitable for finding the optimal solution? — Dynamic Programming
33. The matrix chain multiplication problem is a classic example solved using: — Dynamic Programming
34. The problem of finding the maximum subarray sum can be solved efficiently using which of the following techniques? — Divide and Conquer
35. Which of the following is a key characteristic of problems suitable for Dynamic Programming? — Overlapping subproblems
36. Backtracking is often implemented using which programming paradigm? — Recursion
37. A problem exhibits 'optimal substructure' if: — Its optimal solution can be constructed from optimal solutions of its subproblems.
38. Which of these algorithms is NOT typically associated with Divide and Conquer? — Dijkstra's Algorithm
39. Which of the following is a characteristic of problems suitable for Divide and Conquer? — Independence of subproblems
40. Which of the following is a key requirement for a problem to be solvable by Divide and Conquer? — Independent subproblems that can be solved recursively
41. Which of the following is a key characteristic of problems suitable for the Greedy approach? — Optimal substructure and the greedy-choice property
42. Branch and Bound is primarily used for solving which type of problems? — Optimization problems
43. In Branch and Bound, a 'branch' operation typically involves: — Generating child nodes from a parent node.
44. Which of the following is a common strategy for Branch and Bound to find the best possible solution? — Depth-first search with pruning
45. When using Dynamic Programming, what is the term for storing the results of subproblems? — Memoization or Tabulation
46. In Dynamic Programming, the two main approaches to storing subproblem solutions are: — Memoization and Tabulation
47. What is the main advantage of using Dynamic Programming over simple recursion for problems with overlapping subproblems? — Reduced time complexity by avoiding recomputation.
48. In the context of Branch and Bound, what is a 'bound' used for? — To prune subtrees that cannot lead to an optimal solution.
49. What is the primary goal of the 'bound' in Branch and Bound? — To estimate the best possible solution in a subtree and prune if it's worse than the current best.
50. When does a simple recursive approach to a problem often become inefficient? — When there are overlapping subproblems that are recomputed multiple times.
All One Line Questions
E-Book Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound. Online Test Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound. Question Bank Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, backtracking and branch-and-bound.