1.1.2Building blocks and problem solving

The three building blocks

Every algorithm is built from three control structures:

• Sequence – steps run one after another.
• Selection (decision) – a condition chooses between paths (if / else).
• Iteration (loop) – steps repeat while a condition holds.

Sequence: one step after another

In a sequence the steps run in the order they are written, each exactly once. The order matters: in "read the price, then calculate the tax", swapping the two steps would calculate tax on a price that does not exist yet.

READ length, width
area = length * width
PRINT area

Selection: choosing a path

Selection asks a question whose answer is true or false (a condition) and follows a different path for each answer. Only one path runs each time.

IF age >= 18 THEN
  PRINT "You may vote"
ELSE
  PRINT "Too young to vote"
END IF

A condition uses comparison operators: =, != (not equal), <, <=, >, >=. Conditions can be joined with AND, OR and NOT, for example marks >= 0 AND marks <= 100.

Iteration: repeating steps

Iteration (a loop) repeats a group of steps. Every loop needs three things, or it will either never run or never stop:

1. A starting value, for example i = 1.
2. A condition that is tested each time, for example i <= 10.
3. A change that moves towards the end, for example i = i + 1.

i = 1
WHILE i <= 5 DO
  PRINT i
  i = i + 1
END WHILE

If you forget step 3, i stays 1, the condition is always true and the loop runs for ever. This is called an infinite loop.

Combining the structures

Real algorithms put the structures inside each other. This is called nesting. For example, to count how many students passed, you loop over the marks (iteration) and test each one (selection inside the loop):

passed = 0
FOR i = 1 TO 30 DO
  READ marks
  IF marks >= 50 THEN
    passed = passed + 1
  END IF
END FOR
PRINT passed

Any algorithm, however large, can be built from just these three structures.

Problem-solving method

1. Understand the problem: what are the inputs, outputs and rules?
2. Plan: write the steps in plain language.
3. Refine into a flowchart or pseudocode.
4. Trace by hand with sample data.
5. Code, run and test.

The method in action

Problem: "A shop gives 10% off any bill of Rs. 5000 or more. Work out the amount to pay."

1. Understand the problem. List the inputs, the outputs and the rules. An IPO table is a simple way to do this:

Ask questions about anything unclear. Is exactly 5000 included? (Yes: "5000 or more".) Can the bill be negative? (No: it should be rejected.)

2. Plan the steps in plain language. Read the bill. If it is 5000 or more, the discount is 10% of the bill, otherwise it is 0. The amount to pay is the bill minus the discount. Display it.

3. Refine the plan into pseudocode or a flowchart:

BEGIN
  READ bill
  IF bill >= 5000 THEN
    discount = bill * 10 / 100
  ELSE
    discount = 0
  END IF
  pay = bill - discount
  PRINT pay
END

4. Trace by hand with test values: a bill of 4000 should give 4000, 5000 should give 4500, and 8000 should give 7200. If any trace gives a different answer, fix the plan before writing code. Tracing is covered in 1.4.1 Trace tables.

5. Code, run and test the program with the same values, and compare the results with your traces.