Chapter 25 Self-Assessment Quiz: Algorithm Design Strategies
Section 1: Multiple Choice
Q1. Which algorithm design strategy solves problems by making the locally optimal choice at each step?
(a) Divide and conquer (b) Greedy (c) Dynamic programming (d) Backtracking
Answer
(b) Greedy algorithms make the locally optimal choice at each step, never backtracking. They are fast but only correct when the "greedy choice property" holds.Q2. Dynamic programming is applicable when a problem has:
(a) Independent sub-problems and linear structure (b) Overlapping sub-problems and optimal substructure (c) No sub-problems (d) A single optimal solution path
Answer
(b) DP requires overlapping sub-problems (same sub-problem appears multiple times) and optimal substructure (optimal solution contains optimal sub-solutions). Without overlap, divide and conquer suffices. Without optimal substructure, DP may not find the optimal solution.Q3. What is the time complexity of the naive recursive Fibonacci compared to the memoized version?
(a) O(n) vs. O(n log n) (b) O(2ⁿ) vs. O(n) (c) O(n²) vs. O(n) (d) O(n!) vs. O(n²)
Answer
(b) Naive recursive Fibonacci is O(2ⁿ) due to redundant recomputation. Memoized Fibonacci is O(n) because each sub-problem is computed once and cached. This is one of the most dramatic performance improvements DP offers.Q4. The fractional knapsack problem can be solved optimally with a greedy algorithm, but the 0/1 knapsack cannot. Why?
(a) The 0/1 knapsack has no sub-problems (b) Greedy cannot handle integer values (c) Taking fractions allows the greedy choice property to hold (d) The 0/1 knapsack is unsolvable
Answer
(c) In the fractional knapsack, taking the highest-value-per-weight fraction first is always optimal because you can take partial items to fill remaining capacity. In 0/1, you must take whole items, so a high-ratio item might use too much capacity, preventing a better combination of smaller items.Q5. The 0/1 knapsack DP has time complexity:
(a) O(n) (b) O(n log n) (c) O(n × W) (d) O(2ⁿ)
Answer
(c) The DP table has n rows (items) and W columns (capacities), and each cell is filled in O(1) time. Total: O(n × W). Note: this is "pseudo-polynomial" because W is the capacity value, not the input size.Q6. Which of these is NOT a divide-and-conquer algorithm?
(a) Merge sort (b) Binary search (c) Dijkstra's algorithm (d) Fast exponentiation
Answer
(c) Dijkstra's algorithm is a greedy algorithm, not divide and conquer. It does not split the problem into sub-problems; it greedily extends the shortest-path tree one vertex at a time.Q7. The difference between memoization and tabulation is:
(a) Memoization is top-down; tabulation is bottom-up (b) Memoization uses more memory (c) Tabulation requires recursion (d) Memoization is always faster
Answer
(a) Memoization starts from the top (original problem) and recurses downward, caching results. Tabulation starts from the bottom (smallest sub-problems) and builds up iteratively. Both achieve the same asymptotic complexity and use similar memory.Q8. For the activity selection problem, the greedy strategy is:
(a) Select the activity with the earliest start time (b) Select the activity with the latest finish time (c) Select the activity with the earliest finish time (d) Select the longest activity
Answer
(c) Selecting the activity that finishes earliest leaves the maximum remaining time for other activities. This is the greedy choice that leads to the maximum number of non-overlapping activities. Earliest start time or longest activity would be suboptimal.Section 2: True or False
Q9. True or False: Every problem that can be solved with dynamic programming can also be solved with brute force (trying all possibilities).
Answer
True. DP is an optimization of brute force. The brute-force approach tries all possibilities (exponential time). DP achieves the same result by eliminating redundant computation through caching. Any problem solvable by DP can be solved by brute force — just much more slowly.Q10. True or False: If a greedy algorithm produces the optimal solution for small inputs, it will produce the optimal solution for all inputs.
Answer
False. Greedy algorithms may produce optimal results on small inputs by coincidence while failing on larger or different inputs. The greedy choice property must be proven mathematically for ALL inputs, not just tested on a few. Always prove correctness before trusting greedy.Q11. True or False: The LCS (Longest Common Subsequence) problem has overlapping sub-problems.
Answer
True. Computing LCS(i, j) may require LCS(i-1, j-1), LCS(i-1, j), and LCS(i, j-1). These sub-problems overlap because, e.g., both LCS(i, j) and LCS(i, j+1) need LCS(i-1, j). This makes DP the appropriate approach.Section 3: Short Answer
Q12. Given coins of denominations {1, 3, 4}, what is the minimum number of coins to make change for 6? Show the DP table.
Answer
DP table: [0, 1, 2, 1, 1, 2, 2]. DP[0]=0, DP[1]=1(1), DP[2]=2(1+1), DP[3]=1(3), DP[4]=1(4), DP[5]=2(1+4), DP[6]=2(3+3). Minimum coins for 6: 2 (using 3+3). Note: greedy would give 4+1+1 = 3 coins — suboptimal!Q13. Name the three "steps" of any divide-and-conquer algorithm and briefly describe each.
Answer
(1) Divide: Split the problem into smaller sub-problems of the same type. (2) Conquer: Solve each sub-problem recursively (or directly if small enough). (3) Combine: Merge the sub-solutions into a solution for the original problem. In merge sort: divide = split array; conquer = sort halves; combine = merge sorted halves.Q14. Why is the 0/1 knapsack DP described as "pseudo-polynomial" rather than truly polynomial? What does this mean?
Answer
The time complexity O(n × W) depends on W, the capacity value. In true polynomial time, complexity depends on the size of the input (number of bits). W requires log₂(W) bits to represent, so O(n × W) is actually O(n × 2^(log W)), which is exponential in the input size. "Pseudo-polynomial" means polynomial in the input values but exponential in the input size. For practical purposes with reasonable W values, this distinction rarely matters.Q15. Describe a real-world problem where you would choose each strategy: (a) divide and conquer, (b) greedy, (c) dynamic programming.