Computer Science › Section F · Algorithms › Topic F.3
Discovering algorithms: problem-solving strategies
Writing an algorithm down is the easy half of programming; finding it in the first place is the hard half. This topic covers the classic phases of problem solving, ways to get started on a problem, and the general strategies that turn up again and again in algorithm design.
Finding the method is the hard part
Building a program involves two jobs: discovering an algorithm that solves the problem and then representing it, as in "Representing algorithms with pseudocode". Discovery is usually harder, because it means finding a way to solve the problem at all. No algorithm can do that for every problem (section M, "Theory of computation", shows some problems have no algorithmic solution), so problem solving stays partly a skill to be practised. Still, good problem solvers share habits and strategies worth learning.
Polya's four phases
In his 1945 book How to Solve It, the mathematician George Polya described four phases of solving a problem: understand the problem; devise a plan; carry out the plan; and look back, checking the solution and asking whether it can solve other problems too. In programming terms: understand what is being asked; form an idea of how some algorithm could answer it; write that algorithm as a program; then test the program's accuracy and ask where else it could be reused. Polya's list still shapes how problem solving is taught.
Phases, not a recipe
Polya's phases describe what a successful solver has done by the end, not a checklist to march through. They overlap and loop back: you may try a plan before you fully understand the problem, and a failed attempt often shows what the problem really asks. Insight can also arrive late. Henri Poincaré described solutions coming to him suddenly after he had put a problem aside, and the quiet time before such an insight is called an incubation period.
Getting a foot in the door
Most strategies share one aim: find a first foothold, then widen it. One way is to work backwards from the desired result towards the starting data, as someone might unfold a paper model to learn how it was folded. Another is to find a related problem that is simpler or already solved and adapt its solution. A third is to solve particular cases by hand and look for the pattern. Sorting one list by hand is not an algorithm, since a program must handle every list, but noticing what you did each time can lead to one.
Stepwise refinement
Stepwise refinement means not tackling the whole task in full detail at once. Break the problem into a few subproblems, break each of those into smaller ones, and continue until every piece is easy to solve. Because it moves from the general to the specific, it is called a top-down method. A bottom-up method goes the other way, building small working parts first and combining them. The two complement each other, and much modern software is assembled bottom-up from ready-made components, as "Software engineering methodologies" explains.
Worked example: the longest rising run
Problem: given daily temperatures, find the longest run of consecutive days on which each day is warmer than the one before. 1. Understand: does a single day count as a run of 1? Yes. Does an equal temperature continue a run? No, it must be strictly warmer. 2. Plan with a special case: for 3, 5, 6, 2, 4, 7, 8, 1 the runs are 3, 5, 6 then 2, 4, 7, 8 then 1, so the answer is 4. By hand, you keep a count that grows while temperatures rise and resets to 1 when they do not, and you remember the biggest count so far. 3. Carry out: write that as a loop over positions 2 to length(L). 4. Evaluate: try an empty list (answer 0), all-equal values (1) and a list that only rises (its full length).
Brute force and greedy strategies
Brute force tries every possibility. It is simple and always finds the answer if one exists, but the possibilities often explode: a four-digit PIN has 10,000 options, while the orderings in which to visit 15 cities number 15!, about \(1.3 \times 10^{12}\). A greedy algorithm makes whatever choice looks best at each step and never reconsiders. Paying an amount with the largest coin that fits, again and again, is greedy, and for US coins it always uses the fewest coins. Greedy methods are fast, but for many problems they miss the best answer, so each one needs a reason to trust it.
Divide and conquer, and dynamic programming
Divide and conquer splits a problem into smaller copies of itself, solves those, often by recursion, and combines the results; binary search, in "Recursive structures: binary search", is an example. Dynamic programming handles problems whose smaller copies overlap: it solves each subproblem once, stores the answer in a table and reuses it. Computing the Fibonacci number F(20) by naive recursion makes 21,891 function calls, because the same values are recomputed over and over; filling a table from F(0) and F(1) upwards needs just 19 additions. The topic "Recursion and structural induction" in Discrete Mathematics explores the naive version.
Worked example: when greedy fails
Suppose coins are worth 1, 5 and 6 cents, and you must pay 10 cents with the fewest coins. 1. Greedy: take 6, leaving 4; 5 does not fit, so take four 1s. That is 5 coins. 2. A check by hand finds 5 + 5, just 2 coins, so greedy is wrong here. 3. Dynamic programming: let Best[a] be the fewest coins for amount a, with Best[0] = 0. For each a, try each coin c that fits: Best[a] = 1 + the smallest Best[a - c]. 4. Filling the table for 0 to 10 gives 0, 1, 2, 3, 4, 1, 1, 2, 3, 4, 2. 5. So Best[10] = 2, matching 5 + 5. Evaluating the greedy plan on a small case (Polya's phase 4) exposed the flaw.
Change your point of view
Familiar tools can hide a simple answer. A knockout tennis tournament has 37 players, with byes where needed. How many matches are played? Drawing the bracket round by round, with byes, is slow and error-prone. Look at it differently: every match knocks out exactly one player, and in the end every player but the champion has been knocked out. So there must be exactly 36 matches, however the bracket is arranged. Asking what each step changes is a habit that pays off in algorithm design too.
Common mistakes to avoid
First, treating Polya's phases as a strict sequence and refusing to experiment until the problem is fully understood. Second, solving one instance, such as sorting one particular list, and calling it an algorithm. Third, trusting a greedy method without testing it on small cases: coins of 1, 5 and 6 cents break it at 10 cents. Fourth, skipping phase 4, so edge cases like an empty list go unchecked. Fifth, reaching straight for heavy machinery, such as equations or a full bracket, when a change of viewpoint gives the answer in one line.
Key takeaways
Discovering an algorithm is harder than representing it, and remains partly an art. Polya's phases are understand, plan, carry out and evaluate, but solvers move back and forth between them. Get a foot in the door by working backwards, solving a related or simpler problem, or studying special cases. Stepwise refinement is top-down; bottom-up building complements it. Brute force tries everything, greedy takes the best-looking step, divide and conquer splits a problem into smaller copies, and dynamic programming stores answers to overlapping subproblems. Always test a plan on small cases.
Flashcards
Flashcard
Finding a method that solves a problem
Test your understanding
Question 1 of 5
A student finishes a program and then tries it on an empty list and on a list of identical values. Which of Polya's phases is this?
Question 2 of 5
Coins are worth 1, 4 and 5 cents. What is the fewest number of coins that make exactly 8 cents?
Question 3 of 5
A knockout tournament has 50 players, with byes where needed. How many matches are played in total?
Question 4 of 5
Which description fits stepwise refinement?
Question 5 of 5
What is the longest run of strictly rising values in 9, 4, 6, 6, 7, 8, 2?
