Algorithm Design and Problem-solving

Paper 2 is entirely about solving problems and writing pseudocode. This chapter sets out the thinking skills and the ways of writing down an algorithm. Chapters 10 and 11 add data structures and the full pseudocode toolkit, and chapter 12 covers the software development process.

9.1 Computational thinking skills

Computational thinking is solving a problem in a way that a computer can carry out. Two key skills:

Abstraction

Abstraction means keeping the details that matter for the problem and ignoring (hiding) the ones that do not. It reduces the amount of detail, so the problem is simpler to solve.

Abstraction is used in the identifiers and data types chosen (a Student record keeps a name and a mark, not the person's whole life), in procedures and functions that hide how something is done (you call CalculateTax() without needing to see the code), and in models and simulations.

Benefits of abstraction. It reduces complexity, so the problem is easier to understand and solve; it keeps attention on what matters; a general solution can be reused for similar problems; and a programmer can use a module without knowing how it works. To produce an abstract model of a system, list the essential features and leave out the rest. For a bus timetable program the stops, times and routes are essential; the colour of the buses and the names of the drivers are not.

Decomposition

Decomposition means breaking a large problem into smaller, simpler sub-problems, which can be solved separately and then combined. It makes a big project manageable.

Benefits: each part is easier to understand, write and test; different people can work on different parts at the same time; parts can be reused; and a fault is easier to find. Decomposition leads to a structure chart (chapter 12) and to modules in the program (procedures and functions).

9.2 Algorithms

What an algorithm is

An algorithm is a solution to a problem expressed as a sequence of defined steps. Each step is clear and unambiguous, the steps happen in order, and the algorithm ends. It can be written in several ways. Every algorithm uses combinations of three constructs:

• Sequence: instructions carried out one after another, in order.
• Selection: a decision chooses which instructions to follow (IF, CASE).
• Iteration (repetition): instructions are repeated (a loop).

Structured English

Structured English describes an algorithm in precise, plain-language steps using keywords such as if, otherwise, repeat and until. It is not tied to any programming language and is useful in the design stage.

1. Set the total to zero
2. Repeat the next two steps 10 times:
     a. Ask for a mark
     b. Add the mark to the total
3. Divide the total by 10 to get the average
4. Output the average

Flowcharts

A flowchart shows an algorithm as a diagram. The standard symbols are:

Rules: one START, at least one END; every decision has two labelled exits; arrows show the direction; a loop is a line going back to an earlier point.

A loop in a flowchart: a decision tests the condition, and the "repeat" exit goes back above the decision.

You need to be able to draw a flowchart from structured English or pseudocode, and write pseudocode from a flowchart, by converting the shapes to statements: a rectangle to an assignment, a parallelogram to INPUT/OUTPUT, and a diamond to an IF, WHILE or REPEAT.

Tap to enlarge

A flowchart that reads 10 marks and outputs their average, using a start terminator, process boxes, an input parallelogram, a decision diamond that loops back until the count reaches 10, an output parallelogram and an end terminator, with a key to the flowchart symbols

Close

Pseudocode

Pseudocode is a language-neutral way of writing an algorithm with programming-style statements, without the exact syntax rules of a real language. The Cambridge conventions (the exam insert gives the full list) include:

• Keywords in capitals: INPUT, OUTPUT, IF, THEN, ELSE, ENDIF, FOR, NEXT, WHILE, ENDWHILE, REPEAT, UNTIL, CASE OF, ENDCASE, DECLARE, CONSTANT.
• Assignment with the arrow: Total ← Total + Mark.
• Comparison =, <>, <, >, <=, >=.
• Indentation to show the structure (blocks inside selection and loops).
• Strings in double quotation marks.

DECLARE Total, Mark, Count : INTEGER
DECLARE Average : REAL

Total ← 0
FOR Count ← 1 TO 10
    OUTPUT "Enter mark ", Count
    INPUT Mark
    Total ← Total + Mark
NEXT Count
Average ← Total / 10
OUTPUT "The average is ", Average

Input, process, output: most algorithms follow this pattern. Name the inputs (data supplied), the processing (calculations, decisions, loops) and the outputs (results shown). A good habit when writing: first list these three, then write the steps.

The three basic constructs in pseudocode:

// Sequence
Area ← Length * Width

// Selection
IF Mark >= 50 THEN
    OUTPUT "Pass"
ELSE
    OUTPUT "Fail"
ENDIF

// Iteration (a count-controlled loop, and a pre-condition loop)
FOR Index ← 1 TO 5
    OUTPUT Index
NEXT Index

WHILE Total < 100
    Total ← Total + 10
ENDWHILE

Chapter 11 describes each construct and the other statements in detail.

Identifier names and identifier tables

An identifier is the name of a variable, constant, array, procedure or function. Use meaningful, consistent names such as StudentMark rather than x, with no spaces. An identifier table lists, for each identifier used, its name, data type and a description of its purpose, and is written when designing a solution:

Stepwise refinement

Stepwise refinement (top-down design) is the process of taking a general description and repeatedly breaking each step into more detail until every step can be written directly as a statement in a programming language. It uses decomposition and ends with pseudocode.

Example: Calculate the average of 10 marks.

Level 1:  Get the marks
          Work out the average
          Output the average

Level 2:  Get the marks ->
              Set Total to 0
              Repeat 10 times: input a mark; add it to Total
          Work out the average ->
              Average ← Total / 10
          Output the average ->
              OUTPUT Average

At each level, the steps get more detailed and closer to code. Each part can later become a module (procedure or function).

Trace tables

A trace table records the value of each variable (and any output) as an algorithm is dry run, step by step. It is used to find out what an algorithm does, to test it with sample data, and to find errors.

Method: put one column for each variable (plus a column for output and for any condition); work through the algorithm one statement at a time; write a new row only when a value changes (or each time round a loop), and show the value that results.

Example algorithm:

Total ← 0
FOR N ← 1 TO 4
    IF N MOD 2 = 0 THEN
        Total ← Total + N
    ENDIF
NEXT N
OUTPUT Total

The algorithm adds up the even numbers from 1 to 4. After a trace, state the purpose in one sentence ("it outputs the sum of the even numbers from 1 to 4").

Logic statements

An algorithm's conditions are logic statements: expressions that are TRUE or FALSE, built with comparison operators and the Boolean operators AND, OR and NOT:

IF (Age >= 11) AND (Age <= 16) THEN ...
IF (Day = "Saturday") OR (Day = "Sunday") THEN ...
WHILE NOT (Answer = "Y" OR Answer = "N") ...

Use brackets so the order of evaluation is clear. NOT is carried out first, then AND, then OR, unless brackets change the order. Logic statements are used to define the conditions in selection and in loops, and to define parts of an algorithm precisely (for example "the number is valid if it is between 1 and 100 inclusive").

You may be asked to simplify a logic statement. For example NOT (A > 5) is the same as A <= 5, and NOT (X = 1 OR Y = 2) is the same as X <> 1 AND Y <> 2 (De Morgan's laws).