Introduction to Problem Solving

Solving a problem step by step: analyse it, write an algorithm as a flowchart or pseudocode, code it, test it and debug it, tracing every step with values.

Key ideas

The steps: analyse the problem (inputs, processing, output), develop an algorithm, code it, test it with different inputs, then debug it.
An algorithm is a finite sequence of clear steps; it can be drawn as a flowchart or written as pseudocode.
Every algorithm is built from sequence, selection (IF … ELSE) and repetition (WHILE, FOR).
A dry run traces the algorithm by hand, with a table of every variable updated after each step.
Decomposition breaks a big problem into smaller parts that are solved one at a time.
Two correct algorithms can do different amounts of work: a prime check up to √N needs far fewer divisions than one up to N − 1.

Remember

Flowchart symbols	oval: start or stop; parallelogram: input or output; rectangle: process; diamond: decision
Lines and joins	arrow: the direction of flow; small circle: a connector
Swap A and B	SET temp = A, SET A = B, SET B = temp
Digits of N	N MOD 10 is the last digit and N DIV 10 drops it; R = R × 10 + N MOD 10 reverses N
GCD (Euclid)	WHILE B ≠ 0: R = A MOD B, A = B, B = R; then A is the GCD (48 and 18 → 6)
Prime check of N	up to N − 1: N − 2 divisions; up to √N: (whole part of √N) − 1 divisions
Counting a loop	list the values I takes; the loop stops at the first value that fails the test

Watch out

Starting a sum at 1 or a product at 0: a sum starts at 0, a product at 1.
Writing WHILE I < N where the algorithm needs I <= N: the last value is missed.
Writing SET A = B, SET B = A to swap: both end up equal to the old B.

Worked example

Trace this pseudocode.
1 INPUT N (N = 10)
2 SET S = 0
3 SET I = 2
4 WHILE I <= N
5 SET S = S + I * I
6 SET I = I + 3
7 END WHILE
8 PRINT S
(a) What does it print? (b) How many times does the loop run? (c) What is I when the loop stops?

Working: I: 2, 5, 8, then 11 > 10

Answer: (a) 93; (b) 3; (c) 11