Computational thinking and algorithms

What an algorithm is

An algorithm is a solution to a problem expressed as a sequence of defined steps. The word to hold on to is defined: every step must say exactly one thing, in an order that is fixed, so that anyone following it would do the same thing and get the same result. An algorithm is not written in any particular programming language - it is the logic of the solution, and the same algorithm can be implemented in Python, Java or Visual Basic without changing a single step.

Every algorithm has the same skeleton. It takes input, which is the data it is given or reads, it performs processing, which is the calculation, comparison or storing of that data, and it produces output, which is the result shown to the user, printed or saved to a file. A program that adds two numbers has input (the two numbers), processing (the addition) and output (the total). So does a payroll system, a game or a washing machine controller - only the amount of each changes.

A useful algorithm has to meet a few conditions. It must have a defined start and finish, so it does not run forever by accident. Its steps must be unambiguous, because a step that could be read two ways cannot be programmed. It must be finite - a loop that never ends is a bug, not an algorithm. And it must produce the correct output for every valid input, including the awkward ones: no data at all, the largest value allowed, a value that is out of range. Testing those edge cases is part of designing the algorithm, not something added at the end.

Keep algorithm and program apart, because examiners test the difference. The algorithm is the solution; the program is that solution written in a programming language, with the syntax of that language, so that a computer can run it. A programmer designs the algorithm first and codes it second, because logic errors are far cheaper to find in a diagram or a few lines of pseudocode than in a thousand lines of working code. That is also why algorithms are written down in a language-independent form - so they can be checked, discussed and changed before anyone writes a line of code.

• Algorithm: a solution to a problem expressed as a sequence of defined steps.
• Input - the data the algorithm is given; processing - what it does with the data; output - the result it produces.
• The steps must be unambiguous, in a fixed order, and finite, and the algorithm must be correct for every valid input including the extremes.
• An algorithm is language-independent logic; a program is that algorithm written in a programming language and run on a computer.
• Writing the algorithm down first lets the logic be checked and changed cheaply, before any code exists.

Abstraction: keeping only what matters

Abstraction is the process of removing or hiding the detail that is not needed for a particular purpose, so that only the essential features of a problem or system are represented. The purpose is to make something complicated simple enough to reason about. A real system has an unlimited amount of detail - every rivet, every colour, every measurement to the millimetre - and a person, or a computer model, cannot work with all of it at once. Abstraction decides what is relevant and throws the rest away.

The need for abstraction follows from that. If you tried to model a road network with every lane, kerb and traffic light you would never finish, and you would not be able to answer the simple question you actually asked, which was how long the journey takes. Abstraction makes the problem small enough to solve, and it makes the solution general rather than tied to one specific case: a model of a customer that stores an account number, a name and a balance can be used for every customer in the bank.

An abstract model of a system includes only the essential details. To produce one, you decide what the model is for, then keep the features that affect that purpose and leave out everything else. A model of a car for a driving simulator needs mass, engine power, grip and steering response; it does not need the colour of the paint, the shape of the door handles or the material of the seats. The test is always the same question: if I removed this detail, would the model still answer the question it was built to answer? If the answer is yes, the detail should go.

Abstraction pays for itself in several ways. The model is simpler, so it can be understood and checked by one person. It is quicker and cheaper to build, because far less has to be described. It has fewer errors, because there is less to get wrong. It is easier to change, because a change to one part of a small model has fewer knock-on effects. And it lets you experiment safely: a flight simulator, a structural model of a bridge or a spreadsheet model of a business can be pushed to the point of failure without costing a life or a fortune.

There is a trap, and it is worth a mark on its own. Abstraction is not the same as leaving out whatever you do not understand. If you remove something that does matter to the purpose, the model gives confident wrong answers, which is worse than no model at all. A flight model that ignores wind, or a bank model that ignores overdrafts, is broken. Choosing correctly what is essential is the skill the syllabus is asking for, and it is worth saying so in an answer about benefits.

• Abstraction: removing or hiding detail that is not needed for the purpose, so that only essential features are represented.
• Purpose: to reduce complexity, so that a problem is small enough to understand, solve and model.
• Abstract model: a representation of a system that includes only the details essential to the purpose of the model.
• Benefits: simpler and cheaper to build, easier to understand and test, fewer errors, easier to change, and safe to experiment with.
• Not the same as ignoring detail you do not understand - remove something essential and the model is invalid.

Decomposition: splitting the problem into sub-problems

Decomposition is breaking a large problem down into smaller sub-problems, each of which can be solved separately, until each one is small enough to be written and tested on its own. The sub-problems are chosen by function - what each part has to do - so a school exam-results system splits into reading the marks in, checking that each mark is valid, working out each grade, producing the report and saving the results to a file.

Each sub-problem becomes a program module. In this syllabus a module means a procedure or a function: a named block of code that carries out one job and can be called whenever it is needed. A procedure performs a task and does not return a value - print a report, update a total, save a record. A function performs a task and returns a value to the point where it was called - work out a grade, calculate an average, decide whether a mark is a pass. Modules are given the data they need when they are called, and a function hands its result back to the point where it was called.

The benefits are the ones to write in an answer. Each module is small enough to understand, so one person can hold it in their head and check it. It can be tested in isolation with its own test data, so a wrong grade is traced to one function rather than hunted through the whole system. It can be written by a different member of a team, so work runs in parallel. It can be reused - the same validation procedure serves every input in the program. When something changes, only the module responsible for it changes, which is why a decomposed program is easier to maintain. And an error is contained: a fault in the report module cannot corrupt the marks already stored.

Decomposition is top-down. You start with the whole problem, list the main jobs it involves, then take each job and split it again, and again, until each piece is a single module you could code straight away. That last stage overlaps with stepwise refinement: decomposition decides which pieces the solution is made of, and refinement adds the detail inside each piece until it can be programmed. A strong answer mentions both and keeps the two words apart.

• Decomposition: breaking a problem down into sub-problems, each of which can be solved separately.
• Sub-problems are identified by function - what each part has to do - and each becomes a program module.
• Procedure: a named block of code that performs a task and returns no value.
• Function: a named block of code that performs a task and returns a value.
• Benefits: smaller pieces are easier to understand, test, reuse and maintain; work can be shared across a team; faults are isolated to one module.

Identifiers and the identifier table

An identifier is the name a programmer gives to a piece of data or to a module - a variable, a constant, an array, a procedure or a function. The name is for the human reading the program, not for the computer, so it should say what the data is. TotalScore is suitable; x and ts1 are not, because six months later nobody, including you, can remember what they hold. Suitable identifiers are meaningful, consistent in style, and unique within their scope.

The practical rules are worth stating plainly. Use a name that describes the contents, such as NumberOfStudents rather than N. Use one convention throughout - capitalising each word, or separating words with an underscore - and never mix the two. Do not use spaces, punctuation or a name that starts with a digit. Do not use a reserved word such as IF, THEN, FOR or OUTPUT, because the language will refuse it. Avoid misleading abbreviations (Weight and Wait are too easy to confuse) and avoid a name so long that it hides the logic. A constant should look different from a variable, usually by being in capitals, so a reader can see at a glance that it does not change.

An identifier table is the design document that goes with the algorithm. It lists every identifier the solution will use, what it holds and what data type it is. It is drawn before the pseudocode is written, and it does two jobs: it forces you to decide the data types early, and it stops the same idea being given two different names in two different modules. In an exam it also earns marks on its own, so never answer a pseudocode question without one when the question invites it.

A complete identifier table has one row per identifier and three columns: the identifier, a description of what it represents, and its data type, chosen from INTEGER, REAL, CHAR, STRING, BOOLEAN or DATE. Choose the type that fits the values the data can actually take: a count of students is an INTEGER, a price is a REAL because it has pence, a name is a STRING, and a yes/no flag is a BOOLEAN. Getting the type wrong is not cosmetic - it decides whether a calculation rounds or truncates, and whether a comparison behaves as you expect.

The three constructs: sequence, selection and iteration

Every algorithm, however large, is built from three basic constructs. Sequence is steps carried out one after another in the order written. Selection is a choice between alternatives, taken because a condition is either true or false. Iteration (repetition) is carrying out a group of steps more than once. If you can write these three and combine them, you can write any algorithm in this course - there is nothing else.

Sequence needs no keywords, only discipline: the statements run top to bottom, so the order matters. Reading a value into Total before setting Total to zero wipes the value you just read, and no compiler will warn you. Selection is written with IF ... THEN ... ELSE ... ENDIF. The condition is a logic statement that evaluates to TRUE or FALSE; if it is true the statements after THEN run, otherwise the statements after ELSE run, and the ENDIF marks where the two paths join again. Nested IFs handle more than two cases, and CASE OF ... OTHERWISE ... ENDCASE is the tidier form when one value has several possible matches.

Iteration comes in two families, and the exam expects you to choose correctly. Count-controlled iteration is FOR ... TO ... NEXT, used when the number of repetitions is known before the loop starts - process 20 students, print 12 months. Condition-controlled iteration repeats until some condition changes, and there are two forms that students constantly confuse. WHILE ... DO ... ENDWHILE tests the condition at the start, so if the condition is false first time the loop body never runs at all. REPEAT ... UNTIL tests the condition at the end, so the body always runs at least once. Use WHILE when there might be nothing to process, and REPEAT when you must ask at least once, such as a menu or a password prompt.

One rule catches more marks than any other: something inside the loop must change the value being tested, or the loop never ends. A WHILE Count < 10 DO loop whose body never adds 1 to Count is an infinite loop, and an answer containing one is a wrong algorithm however neat it looks. That is an algorithm design error, not a typing error, and it is the single most common fault in candidate pseudocode.

• Sequence: statements executed one after another, in the order written.
• Selection: IF ... THEN ... ELSE ... ENDIF, or CASE OF ... OTHERWISE ... ENDCASE where one value has several cases.
• Count-controlled iteration: FOR Index <- 1 TO 10 ... NEXT, when the number of repetitions is known.
• Condition-controlled, test at start: WHILE ... DO ... ENDWHILE - may run zero times.
• Condition-controlled, test at end: REPEAT ... UNTIL - always runs at least once.
• Every loop must change the value it tests, or it never terminates.

Documenting an algorithm: structured English, flowcharts and pseudocode

An algorithm has to be written down so that other people can read it, check it and code it. The syllabus gives three ways of documenting one: a structured English description, a flowchart, or pseudocode. They are three views of the same logic, and a question may ask you to produce any one of them from any other.

A structured English description is a numbered list of steps in ordinary English, using the words of the three constructs - INPUT, IF ... THEN ... ELSE, REPEAT ... UNTIL - without any programming syntax. It is the version a client or a manager can read and agree with, which is why it is used at the start of a project to check that the programmer has understood the requirement. It is less precise than pseudocode: English can be read two ways, which is exactly what pseudocode exists to prevent.

Pseudocode is a structured, language-independent notation with strict-ish rules. It has keywords for input, output, assignment, selection and iteration, and indentation shows which statements belong inside a loop or an IF. It is not a real language, so there is no compiler to complain about a missing semicolon, but it must still be unambiguous and it must still be complete: every identifier you use should appear in the identifier table, and every loop should be closed with its ENDWHILE, UNTIL or NEXT.

A flowchart is a diagram of the same logic, drawn with a small set of standard symbols and arrows. It shows the shape of the solution at a glance - where the branches split and where the loops go back - which is why it is the best tool for talking through a design with someone else.

Converting between the three representations

Converting is mechanical once you know the mapping, and the mapping is one table. INPUT and OUTPUT become parallelograms. An assignment or a calculation becomes a rectangle. IF ... THEN ... ELSE becomes a diamond with YES and NO on its two exits. A WHILE or a REPEAT becomes a diamond whose NO or YES exit goes back up to an earlier point in the chart. START and STOP become terminators.

Work through a small example. A gym charges 5 pounds for a member or for anyone under 18, and 8 pounds for everyone else. As structured English: 1. INPUT Age. 2. INPUT IsMember. 3. IF Age < 18 OR IsMember = TRUE THEN Price <- 5 ELSE Price <- 8. 4. OUTPUT Price. The pseudocode below is the same solution written line by line, and note that the IF line ends with THEN, the two branches are indented, and ENDIF closes the structure.

The same logic as a flowchart reads: START terminator, then a parallelogram reading Age, then a parallelogram reading IsMember, then a diamond asking Age < 18 OR IsMember = TRUE; the YES exit leads to a rectangle setting Price to 5, the NO exit leads to a rectangle setting Price to 8, both rectangles join, then a parallelogram outputs Price, and a STOP terminator ends it. If you can narrate a chart like that, you can draw one from any description.

When converting, work in a fixed order and do not skip steps. First list the inputs, then the outputs, then the processing that turns one into the other. Identify every decision and give each one two labelled exits. Identify every repetition and make its arrow return to the right place - back to the condition, not to the first line of the algorithm. Finally trace two or three paths through your own answer, one that takes each branch, and check that every path reaches STOP. Most conversion marks are lost by missing an input, by putting a calculation in a diamond, or by leaving a branch that never terminates.

• INPUT / OUTPUT -> parallelogram; calculation or assignment -> rectangle; condition -> diamond with YES and NO; START / STOP -> terminator.
• A loop is a diamond with one arrow going back to an earlier symbol - the condition, not the first line.
• Work in order: inputs, then outputs, then processing, then decisions, then loops.
• Every path through the chart must reach STOP, and every diamond must have two labelled exits.

Stepwise refinement

Stepwise refinement is the process of taking an algorithm expressed at a high level and breaking each step into more and more detail, one level at a time, until every step is a single instruction that can be programmed. The stopping point is defined by the syllabus phrase a level of detail from which the task may be programmed: you stop when a programmer could code each line without having to make any further design decisions.

The first level states the job in a few broad steps, some of which are far too vague to code. A step such as calculate the wages hides decisions - how many hours were worked, what the hourly rate is, whether overtime is paid, what happens at exactly 40 hours. Refinement replaces that one step with several, each simpler, and then refines again if any of those is still too vague.

For a wages program, level 1 is: input the hours worked, input the hourly rate, calculate the pay, output the pay. Level 2 refines calculate the pay into: if hours are 40 or fewer, pay is hours x rate; otherwise pay is 40 x rate plus the extra hours x rate x 1.5. Level 3 refines each of those into readable pseudocode, and now every line can be typed. Three levels, each one adding detail to the level above, without ever rewriting what was already decided.

Work top-down and keep the structure visible by indenting each level under the step it refines, and by numbering steps 1, 1.1, 1.2. That way the refinement can be checked level by level, and the structure of the finished algorithm is the structure you designed. The benefits to quote: each level is easy to check against the level above, the detail is added in manageable amounts, the sub-steps that emerge are natural candidates for modules, and a change at one level is confined to that part of the design. It also lets you stop and confirm the design with the person who asked for the program before the expensive detail is added.

• Stepwise refinement: adding detail to an algorithm one level at a time until each step can be programmed directly.
• Stopping point: the level of detail from which the task may be programmed - no design decisions left for the coder.
• Work top-down, indenting or numbering each level under the step it refines (1, 1.1, 1.2).
• Refined sub-steps are natural modules, so refinement and decomposition support each other.
• Benefits: each level can be checked against the one above, detail is added in manageable amounts, and changes stay local.

Logic statements in an algorithm

A logic statement is an expression that evaluates to TRUE or FALSE. It is what a decision or a loop condition is made of, so the correctness of the whole algorithm depends on them. A logic statement is built from a comparison of two values, and comparisons can be combined with AND, OR and NOT.

The comparison operators are = (equal to), <> (not equal to), <, >, <= and >=. Note that = compares and does not assign: assignment in pseudocode is <-, so Total <- Total + 1 changes Total while Total = 10 asks whether it is ten. Mixing the two up produces an algorithm that either never loops or loops forever, and it is a very common slip in exam answers.

The combining operators behave as you would expect, but their precedence matters. NOT is applied first, then AND, then OR, so IF A OR B AND C THEN is read as A OR (B AND C), not as (A OR B) AND C. Do not rely on the reader remembering that: put the brackets in. A compound condition with brackets is clearer, and clarity is what a mark scheme rewards.

Logic statements are used in three places. In selection, to choose a path: IF Mark >= 40 AND Attendance >= 80 THEN. In iteration, to decide whether to go round again: WHILE NOT Found AND Count <= 100 DO. And in flags, a Boolean variable that records that something has happened - Found <- TRUE - so that a later condition can test it without repeating the whole comparison. A flag plus a logic statement is how you search a list and stop as soon as the item is found.

• Comparison operators: =, <>, <, >, <=, >=. = compares; <- assigns.
• Combining operators: AND (true only if both sides are true), OR (true if either side is true), NOT (reverses the value).
• Precedence: NOT, then AND, then OR - put brackets in compound conditions so the meaning is unambiguous.
• Use logic statements in selection conditions, in loop conditions, and with Boolean flags that record whether something has been found.