B. Software Development · Software Development: Problem Solving, Design, Testing and the Life Cycle

Problem-Solving Strategies for Programmers

B1.1About 70 minutes

Learning goals

I can name and describe the problem-solving strategies programmers use: stepwise refinement, divide and conquer, working backwards, examples, extreme cases, tables and charts, and trial and error.
I can break a big programming task into smaller steps until each step is easy to code.
I can choose a strategy that suits a problem and explain why I chose it.
I can use a four-step plan (understand, plan, carry out, look back) on a new problem.

Words to know

problem-solving strategy
A general plan of attack you can use on many different problems, such as working backwards or making a table.

stepwise refinement
Starting with the whole task in one sentence, then breaking it into steps, then breaking each step into smaller steps, until every step is simple enough to code. Also called top-down design.

divide and conquer
Splitting a problem into smaller parts of the same kind (or independent parts), solving each part, then combining the results.

working backwards
Starting from the result you want and reversing the steps to find what you need at the start.

extreme case
An input at the edge of what is allowed, such as 0, an empty list, a negative number or a very large value. Also called an edge case or boundary case.

trial and error
Trying a possible answer, checking it, and using what you learn to make a better try. A program can do this very fast and very systematically.

algorithm
A precise, finite list of steps that solves a problem.

Coding starts before you type

Picture a snow day. You want to build a program that tells your hockey league who is in first place. You open your editor... and stare at a blinking cursor. Where do you even start?

Experienced programmers almost never start by typing code. They start by thinking about the problem with a few trusted strategies. A strategy is a general plan of attack. It is not tied to one problem. The same strategy that plans a hockey program can plan a recipe app or a game.

In this lesson you will learn the strategies named in the Ontario curriculum: stepwise refinement, divide and conquer, working backwards, examples, extreme cases, tables and charts, and trial and error. You will use all of them again and again in the rest of this course.

Remember from earlier units

In the Programming Basics unit you wrote programs with variables, input(), print(), if statements and loops. In Arrays and Subprograms you used lists and wrote your own functions with def. This unit is about how to plan and build programs with those tools. If you studied Grade 9 math on this site, you have also already used for and while loops to search for answers.

A four-step plan for any problem

The mathematician George Pólya described a famous four-step plan in his 1945 book How to Solve It. Programmers still use it:

Understand the problem. What are the inputs? What output is wanted? What are the rules? Can you say the problem in your own words?
Make a plan. Pick one or more strategies from this lesson.
Carry out the plan. Write the algorithm, then the code.
Look back. Test it. Does the answer make sense? Could the plan be simpler? Could you reuse it?

The strategies below mostly help with step 2.

Strategy 1: Stepwise refinement (top-down design)

Write the whole task as one sentence. Then split it into 3 to 5 big steps. Then split each big step into smaller steps. Keep going until every step is so small that you could write it as one or two lines of code. Each round of splitting is called a refinement.

Here is the hockey task refined twice. In this league, a win is worth 2 points and an overtime loss is worth 1 point.

Stepwise refinement turns one big sentence into small, codeable steps. Read the tree from the top down; each level adds detail to the level above.

name = "Huskies"

w = 11

otl = 3

points = 2 * w + 1 * otl

print(name, "have", points, "points")

Output: Huskies have 25 points

Strategy 2: Divide and conquer

Divide and conquer means: split the problem into smaller pieces, solve the pieces, then combine the answers. There are two flavours:

Split into independent parts. A quiz app has a part that asks questions, a part that marks answers and a part that shows a score. Different people (or different functions) can build each part.
Split into smaller copies of the same problem. To find a number between 1 and 100, guess the middle. Whatever the answer ("too high" or "too low"), half the numbers are gone. Now you have the same problem, only half the size. Keep halving.

Divide and conquer: finding the secret number 42 between 1 and 100. Each guess is the middle of the shaded range, and each answer throws away about half of the range. It took 7 guesses.

Because each guess halves the range, 7 guesses are always enough for 1 to 100: after 7 halvings, 100 numbers shrink to 1 (2⁷ = 128, which is more than 100). Guessing 1, 2, 3, ... in order could take 100 guesses. A clever plan beats a fast typist!

Strategy 3: Working backwards

Some problems tell you the end and ask about the start. Then reverse each step, in reverse order. Undo "add" with "subtract", undo "multiply" with "divide".

Worked example

Example 1: Working backwards

A gift card is used three times. First, $12 is spent. Then half of what is left is spent. Then $5 is spent. Now $8 remains. How much was on the card at the start? Plan the calculation a program could do.

Write the forward steps: start → subtract 12 → halve → subtract 5 → 8.
Reverse the order and undo each step: start from 8, undo "subtract 5" by adding 5: 8 + 5 = 13.
Undo "halve" by doubling: 13 × 2 = 26.
Undo "subtract 12" by adding 12: 26 + 12 = 38.
Look back: check forwards. 38 − 12 = 26, half of 26 is 13, 13 − 5 = 8. ✓

The card started with $38. In code: start = (8 + 5) * 2 + 12.

Strategy 4: Examples, extreme cases, tables and charts

Work examples by hand. Before coding "find the average of some marks", average 3 marks yourself. You will notice exactly which steps a program needs (add them up, count them, divide).
Try extreme cases. What if there are zero marks? What if a mark is negative, or 100, or 1 000 000? Extreme cases expose bugs and missing rules. (Dividing by a count of zero would crash a program!)
Make a table or chart. Organizing small examples in a table often reveals a pattern you can turn into a formula or a loop.

Worked example

Example 2: A table reveals the pattern

Every player on a team high-fives every other player exactly once after a win. How many high-fives happen with n players? Find a formula a program can use.

Work small examples and record them in a table: 2 players → 1 high-five; 3 players → 3; 4 players → 6; 5 players → 10.
Look for a pattern in the differences: 1, 3, 6, 10 grows by 2, 3, 4. Each new player high-fives everyone already there.
Reason it out: each of the n players high-fives the other n − 1 players, which counts each high-five twice (once for each person). So the total is n(n − 1) ÷ 2.
Check against the table: n = 5 gives 5 × 4 ÷ 2 = 10 ✓. Extreme cases: n = 1 gives 0 ✓ and n = 0 gives 0 ✓.

High-fives = n(n − 1) / 2. A 20-player roster gives 20 × 19 ÷ 2 = 190 high-fives.

Players n	2	3	4	5	6
High-fives	1	3	6	10	15

Small examples organized in a table. The pattern leads to the formula n(n − 1) / 2.

Strategy 5: Trial and error (guess and check)

When you cannot see a formula, try an answer, check it, and improve. People do this slowly. Computers do it millions of times a second, so a program can try every possibility in a range. This systematic trial and error is called a brute-force search.

Worked example

Example 3: Let the computer do the trials

Two consecutive whole numbers multiply to 1332. What are they?

Understand: we want n and n + 1 with n × (n + 1) = 1332.
Plan: try every n from 1 to 99 and print any that work. 99 × 100 = 9900 is far more than 1332, so the answer must be in this range.
Carry out: the loop below checks each n.
Look back: 36 × 37 = 1332 ✓. Only one n printed, so there is only one answer in the range.

36 and 37.

for n in range(1, 100):

if n * (n + 1) == 1332:

print(n, n + 1)

Output: 36 37

Strategy	Use it when...	Quick example
Stepwise refinement	the task is big and vague	planning a quiz app from one sentence
Divide and conquer	the problem splits into parts, or into smaller copies of itself	halving to find a number from 1 to 100
Working backwards	you know the end result and need the start	how much was on the gift card
Examples / extreme cases	you need to understand the rules or test a plan	average of 0 marks
Tables and charts	you suspect a pattern	high-fives for n players
Trial and error	no formula is obvious but the possible answers can be listed	consecutive numbers with product 1332

Choosing a strategy. Many real problems use two or three strategies together.

Just for fun

How many programmers does it take to change a light bulb?

None. That's a hardware problem.

Hands-on activity

Halving at the kitchen table

You need: a family member or friend, paper and a pencil.

Your partner secretly picks a whole number from 1 to 100 and writes it down.
Guess using divide and conquer: always guess the middle of the numbers still possible. (If 1 to 49 are left, guess 25.) Your partner answers only "higher", "lower" or "yes".
Record each guess and the range left, like the picture above. Count your guesses. You should never need more than 7.
Swap roles. This time your partner guesses randomly. Compare the number of guesses.
Look back: write two sentences about why halving wins. Then predict: how many guesses would 1 to 1000 need? (Hint: 2¹⁰ = 1024.)

What to look for: the halving guesser always finishes in 7 or fewer guesses; for 1 to 1000 the answer is 10.

Your turn

Name the four steps of Pólya's problem-solving plan.

Use stepwise refinement to break "Make a program that converts a temperature in Celsius to Fahrenheit" into three steps. Use F = 9C ÷ 5 + 32.

A number is doubled, then 7 is subtracted, and the result is 29. Work backwards to find the number.

Using halving, what is the greatest number of guesses needed to find a secret number from 1 to 50?

You are planning a program that finds the largest number in a list of marks. Name two extreme cases you should think about.

Which strategy is the loop for n in range(1, 100): if n * n == 2025: print(n) using? What does it print?

Make a table for the number of squares in a row of n toothpick squares (n = 1, 2, 3, 4) and the number of toothpicks used: 4, 7, 10, 13. Find a formula.

More practice: warm-up

What is an algorithm?

True or false: stepwise refinement starts with small details and builds up to the big picture.

Which strategy uses "undo the last step first"?

A program asks for someone's age. Give one extreme case to test.

Name the strategy: "Try 1, then 2, then 3, ... and check each one."

More practice: on your own

Refine the step "Display a times table for a number" into smaller steps a program could follow.

A video game score is tripled, then 50 is added, then the result is halved, giving 100. What was the original score? Show your reasoning.

How many guesses does halving need for a number from 1 to 1 000 000? Explain.

A school club is building a ticket app. Explain how divide and conquer helps a team of three build it.

Find the smallest whole number n for which 2ⁿ is greater than 5000. Which strategy did you use, and what would a program look like?

Challenge

Diagonals of a polygon: a triangle has 0, a square 2, a pentagon 5, a hexagon 9. Use a table and reasoning to find a formula for an n-sided polygon, and check it for the hexagon.

A brute-force program checks every 4-digit PIN (0000 to 9999) and can check 100 PINs per second. What is the longest it could take? How would working out an extreme case help a designer of a phone lock?

Write a brute-force loop (in words or Python) to find all whole numbers x from 1 to 50 for which x² − 10x + 21 = 0. Then give the answers.

Check your understanding

Quiz

Which strategy begins by writing the whole task as one sentence and then adding detail level by level?

A number is multiplied by 4, then 6 is added, giving 50. Working backwards, what was the number?

Using halving, what is the most guesses needed to find a number from 1 to 100?

Which input is the best example of an extreme case for a program that averages a list of marks?

A loop tries every value of n from 1 to 1000 and prints the ones that satisfy a condition. This is an example of:

With 6 players, how many high-fives happen if everyone high-fives everyone else once?

For parents and teachers

Big idea: Expectation B1.1 asks students to use a range of problem-solving strategies (stepwise refinement, divide and conquer, working backwards, examples, extreme cases, tables and charts, trial and error). These are thinking habits, not Python features, so this lesson can be done mostly on paper.

How to help: Play the halving guessing game together; it is the clearest picture of divide and conquer. When your teen is stuck on any assignment, ask "Can you say the problem in your own words?" and "Have you tried a small example by hand?" Those two questions solve a surprising number of problems.

Common difficulties:

Jumping straight to typing code. Insist on a written plan (a refinement tree or a list of steps) first.
Working backwards but forgetting to reverse the order of the steps.
Thinking trial and error is "cheating". A systematic search is a legitimate algorithm when the number of possibilities is reasonable.
Skipping extreme cases. Ask "What if the input is zero, empty or huge?" every time.