Card 06/ 07
Practice: Naming the Strategy for Four Problems
A route planner, a tournament draw, a puzzle solver and a coin machine each need a different strategy.
Naming the strategy for a problem means finding its subproblems first and then asking which of the four properties they have. This exercise gives four problems, each of which needs a different strategy; for each, name the subproblems, pick the strategy, and say what would make each of the others fail.
- A puzzle solver. List every way to fill a small grid with digits so that the puzzle's rules hold.
- A route planner. A car with a fixed range drives along one road with fuel stations at known distances. Find the fewest stops that get it to the end. Stopping at the farthest station it can reach each time can be proved safe by an exchange argument.
- A coin machine. Pay an amount in the fewest coins, where the coins are 1, 4 and 6. The amount 8 is a good one to test any rule on.
- A tournament draw. Find the champion of a knockout tournament, where the two halves of the draw are played apart and their winners meet once in the final.
Name a strategy for each problem, with a reason, then compare.
| Problem | Subproblems | Strategy | Why not the others |
|---|---|---|---|
| Puzzle solver | The grid with some cells filled | Backtracking | Every filling must be listed, and a table or a greedy rule keeps one answer per subproblem |
| Route planner | The rest of the road from the last stop | Greedy | A table over every station would also work but tries choices the exchange proof has already ruled out |
| Coin machine | The fewest coins for each smaller amount, which recur | Dynamic programming | Largest first pays 8 as 6 + 1 + 1, 3 coins, where 4 + 4 needs 2; no proof makes a greedy rule safe here |
| Tournament draw | Each half of the draw, which shares no players with the other | Divide and conquer | No half is ever decided twice, so a memo would never be used |
The coin counts are from a run: with 1, 4 and 6, the fewest coins for 8 is 2 and largest first uses 3. The order of the decision settles any doubt. The puzzle needs every candidate, which only backtracking provides. The route planner has a proof, so it is greedy before a table is considered. The coin machine has no proof and repeating amounts, so it takes a table. The tournament's halves share nothing, which is the case left once overlap is ruled out.
← → move through sections and cards