Design Techniques - divide and conquer, dynamic programming, greedy algorithms, backtracking, branch and bound - Question Bank
1. Which technique is generally preferred for solving the 0/1 Knapsack problem over a greedy approach because the greedy choice property does not hold?
2. 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?
3. Which design technique is based on the principle that the optimal solution to a problem contains optimal solutions to its subproblems?
4. 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:
5. Which of the following is a common strategy used in Dynamic Programming to avoid recomputing subproblems?
6. What is a key characteristic of problems suitable for Branch and Bound?
7. The problem of finding the shortest path in a Directed Acyclic Graph (DAG) can be efficiently solved using:
8. Which technique is used in algorithms like Prim's and Kruskal's for finding Minimum Spanning Trees?
9. What is the time complexity of the naive recursive calculation of the nth Fibonacci number?
10. 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:
11. 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?
12. The problem of finding the nth Fibonacci number using recursion without memoization suffers from:
13. What is the primary goal of the 'divide' step in a Divide and Conquer algorithm?
14. Which technique is often used to find all permutations or combinations of a set that satisfy certain conditions?
15. 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:
16. 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?
17. What is the main characteristic of 'overlapping subproblems' in Dynamic Programming?
18. Branch and Bound is particularly useful for solving:
19. Which of the following is an example of a problem solved using Backtracking?
20. What is the 'greedy-choice property'?
21. 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?
22. 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?
23. What is the primary advantage of using a Greedy approach when applicable?
24. The problem of finding the maximum value in the 0/1 Knapsack problem is typically solved using:
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?
26. The Floyd-Warshall algorithm, which finds all-pairs shortest paths, is an example of which design technique?
27. What is the 'state space tree' in the context of Backtracking?
28. 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?
29. In Branch and Bound, what is the purpose of a 'bound'?
30. The problem of finding the Longest Common Subsequence (LCS) is a classic example solved using:
31. 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?
32. What does 'optimal substructure' mean in the context of Dynamic Programming?
33. Which technique is generally used for optimization problems where the solution space is structured as a tree?
34. The Fractional Knapsack problem is optimally solved using which technique?
35. Which of the following algorithms is NOT typically considered a Divide and Conquer algorithm?
36. What is the primary difference between memoization and tabulation in Dynamic Programming?
37. The 8 Queens puzzle is a classic problem often solved using:
38. 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?
39. The problem of finding the minimum number of coins to make a given amount of change is typically solved using which technique?
40. When using Dynamic Programming, building the solution from the smallest subproblems up to the original problem is known as:
41. Which technique is often described as a form of depth-first search in the state space tree?
42. 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?
43. Which of the following is a classic example of a problem solved efficiently using the Divide and Conquer technique?
44. 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?
45. 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?
46. Dynamic Programming is most effective when a problem exhibits which two properties?
47. Which algorithm design paradigm is characterized by making the locally optimal choice at each stage with the hope of finding a global optimum?
48. In the context of Divide and Conquer, what is the primary goal of the 'combine' step?
49. Which design technique involves breaking down a problem into smaller, independent subproblems of the same type, solving them recursively, and then combining their solutions?