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