Algorithm Design and Problem-Solving

• The four sentences that hold Topic 7 together. (1) Analysis, design, coding, testing — and you are allowed to go back. (2) Structure diagram, flowchart and pseudocode are three ways of writing one solution. (3) Validation checks a rule, verification checks a copy, testing checks the whole algorithm. (4) A trace table is filled in one executed statement at a time.
• The four that cost the most marks. Coding is not the first stage. Extreme data is accepted. A maximum must not start at zero. And valid is not the same as correct.

• Name the four stages of the program development life cycle in order, and sort a described task into the correct stage.
• Define abstraction and decomposition precisely, and explain the difference between them with an example.
• Explain that a computer system is made of sub-systems which are themselves made of further sub-systems, and draw a structure diagram that shows this.
• Identify the inputs, processes, outputs and storage of a described problem, without confusing a stored value with an output.
• Read and draw a flowchart using the six official Cambridge symbols, with both branches of every decision labelled.
• Write algorithms in Cambridge pseudocode using the official identifier style, assignment arrow, operators, block keywords and indentation.
• State the overall purpose of a given algorithm and describe the processes it uses, rather than paraphrasing its first line.
• Apply and trace all seven standard methods: linear search, bubble sort, totalling, counting, maximum, minimum and average.
• Choose and justify the correct validation check from range, length, type, presence, format and check digit — and state its limitation.
• Distinguish validation from verification, and describe the visual check and the double entry check.
• Produce normal, abnormal, extreme and boundary test data for a stated rule, with the expected result for each value.
• Complete a trace table for sequence, selection and iteration, recording variables, conditions, outputs and user prompts.
• Find a logic error in a given algorithm, explain its effect, correct it exactly, and choose data that retests it.
• Write and amend algorithms in pseudocode and flowchart form for problems of increasing size.

The scenario. A school records house points at the end of each term. There are six houses — Ash, Birch, Cedar, Elm, Fir and Oak — and each has a whole-number score from 0 to 200 inclusive. The office needs a program that accepts the six scores, rejects any that are out of range, and then reports the total, the average, the winning house, and the six houses listed in order. Staff must also be able to check whether a particular score was achieved by anyone. The six scores used throughout the worked answers are: Ash 148, Birch 92, Cedar 175, Elm 92, Fir 130, Oak 161.

Inputs, Processes, Outputs and Storage

Inputs, processes, outputs and storage — IPOS — is the four-way analysis of a problem, separating the data supplied to a system, the calculations and decisions performed on it, the results reported to the user, and the values kept for later use.

Decomposition

Breaking a complex problem down into smaller, more manageable sub-problems, each of which can be understood, designed, implemented and tested separately before the parts are combined into the complete solution.

Pseudocode

A structured way of writing an algorithm that uses program-like statements for assignment, selection, iteration, input and output but belongs to no particular programming language; Cambridge pseudocode uses upper-case keywords, Pascal-case identifiers, a left arrow for assignment and named block-ending keywords such as ENDIF, NEXT and ENDWHILE.

Algorithm Representations

Algorithm representations are the three interchangeable ways of setting out one algorithm — a structure diagram showing the breakdown into subtasks, a flowchart showing the order and branching of steps, and pseudocode showing the statements in program-like form.

Verification

A check that data has been copied or entered accurately and matches the original source, carried out either by a visual check in which a person compares the entered data with the source, or by a double entry check in which the data is entered twice and the two versions are compared; verification confirms accurate copying, not that the data is reasonable or that the source was correct.

Program Development Life Cycle

The sequence of stages a program passes through from problem to tested solution, limited in this syllabus to analysis, design, coding and testing, where analysis identifies the problem and requirements using abstraction and decomposition, design records the solution as structure diagrams, flowcharts or pseudocode, coding writes the program code with iterative testing, and testing runs the program with chosen test data and compares actual results with expected results.

Synthesis Scenario

A synthesis scenario is an extended problem that requires the whole chapter at once — decomposition, IPOS analysis, algorithm design, standard methods, validation, test data, tracing and correction — applied to a single situation rather than to separate short questions.

Writing and Amending Algorithms

Writing and amending algorithms is the production of a complete algorithm for a stated problem, and the modification of a given algorithm so that it meets a changed requirement, expressed either in pseudocode or as a flowchart.

Choosing a Standard Method

Choosing a standard method is matching the wording of a requirement to the technique it demands — totalling, counting, maximum, minimum or average — and recognising the requirements that need two of them working together.

Structure Diagram

A hierarchical design diagram that shows a system at the top and its sub-systems on the levels below, with each sub-system broken down further where necessary; it shows what the parts of a solution are and how they nest, not the order in which steps are carried out.

Linear Search

A standard method of solution that examines the items of a collection one at a time starting at the first, compares each item with the value being searched for, and stops when a match is found or when the end of the collection is reached; it does not require the data to be in any particular order and must report a not-found result when no match exists.

Accumulator Methods

Accumulator methods are the five standard techniques that build a result across a set of values — totalling, counting, finding a maximum, finding a minimum and calculating an average — each depending on a correctly chosen initial value before the loop begins.

Algorithm

A finite, ordered and unambiguous sequence of steps that solves a problem or completes a task; it is a logical solution independent of any programming language, and it may be recorded as a structure diagram, a flowchart or pseudocode.

Abstraction

The process of keeping only the details that are relevant to the solution of a problem and removing the details that are not relevant, so that the resulting representation is simpler to work with while still answering the question asked.

Explaining an Algorithm's Purpose

Explaining an algorithm's purpose is stating what it accomplishes overall and describing the processes it uses to do so, judged by reading the whole algorithm rather than by paraphrasing its opening line.

Validation

An automatic check carried out by a computer as data is entered, to make sure the data satisfies stated rules such as being within a range, of a required length, of an expected data type, present at all, in a required format, or consistent with a calculated check digit; validation establishes that data is reasonable, not that it is correct.

Sub-system

A self-contained part of a larger computer system that performs an identifiable function, can be designed, implemented and tested separately from the other parts, and may itself be divided into further sub-systems.

Identifying and Correcting Errors

Identifying and correcting errors is the four-step handling of a faulty algorithm: locating the line at fault, explaining the effect it has on the output, writing the exact corrected line, and choosing test data that would expose the fault if it returned.

Trace Table

A table used to record a dry run of an algorithm, with a column for each variable of interest and further columns for conditions, outputs and user prompts, and a row for each executed step, filled in by following the algorithm exactly one statement at a time rather than by predicting the final result.

Test Data

Data chosen deliberately to test whether an algorithm behaves as intended, classified as normal (valid typical data that should be accepted), abnormal (invalid data that should be rejected), extreme (the largest or smallest acceptable value) and boundary (the largest or smallest acceptable value together with the corresponding smallest or largest rejected value); every test value is paired with an expected result decided before the test is run.

Flowchart

A control-flow diagram in which a terminator marks Start and Stop, a rectangle is a process, a parallelogram is input or output, a diamond is a decision with two labelled outcomes, a rectangle with double side bars is a subroutine call, and arrows show the direction control passes.

Bubble Sort

A standard method of solution that puts a collection into order by repeatedly comparing pairs of adjacent items and swapping them when they are in the wrong order; each complete journey through the collection is a pass, after which the largest remaining value has reached its final position, and passes continue until one pass makes no swaps.

• M1. “Coding is the first stage of the program development life cycle.” Correct Analysis is first, then design, then coding, then testing. Coding is the third stage. Why it matters A program written before the problem is understood solves the wrong problem, and the error is found only at the testing stage, when it is most expensive to fix.
• M2. “The four stages happen once each and never repeat.” Correct The stages always occur in the same order, but development returns to earlier stages when a later one exposes a fault. Why it matters A missing requirement found during testing has to be fixed in analysis, redesigned, recoded and retested.
• M3. “Abstraction and decomposition are the same thing.” Correct Abstraction removes irrelevant detail. Decomposition breaks a problem into smaller sub-problems. Nothing is removed by decomposition and nothing is split by abstraction.
• M4. “Abstraction just means making something simpler.” Correct It means keeping the details that are relevant to the solution and removing the ones that are not. The definition needs both halves.
• M5. “A structure diagram is a kind of flowchart.” Correct A structure diagram shows hierarchy and containment. A flowchart shows control flow. Only the flowchart has arrowheads, decisions and terminators.
• M6. “An algorithm has to be written in a programming language.” Correct An algorithm is a finite, ordered, unambiguous sequence of steps. It can be a flowchart, pseudocode, a structure diagram or ordinary written steps.
• M7. “Flowchart shapes are interchangeable as long as the text is right.” Correct Each of the six symbols has one meaning. A parallelogram is input or output; a rectangle is a process; a diamond is a decision. Using the wrong shape changes what the diagram claims.
• M8. “A decision can have one outgoing line, or three.” Correct A decision produces exactly two lines, representing the two possible outcomes, and both must be labelled Yes/No or True/False.
• M9. “Python syntax is accepted throughout Paper 2.” Correct Where a solution involves coding, answers must be in pseudocode. Python, Visual Basic and Java are permitted only in the final 15-mark scenario question. Why it matters A correct Python answer to an ordinary Paper 2 question is awarded no marks.
• M10. “Pseudocode does not have to be precise because it is not executable.” Correct The syllabus states that precision is required, and gives the example that x > y is acceptable while “x is greater than y” is not.
• M11. “A linear search needs the data to be in order.” Correct It works on data in any order. Sorted data is required by a binary search, which is not in this syllabus.
• M12. “A bubble sort compares any two values.” Correct It compares only adjacent values — Values[Index] with Values[Index + 1] — and swaps them when they are in the wrong order.
• M13. “Counting and totalling are the same thing.” Correct Counting adds one, and only when a condition is met. Totalling adds the value of the item, usually every time.
• M14. “A maximum should always start at zero.” Correct Seed it from the first actual data item. Starting at zero reports 0 as the maximum whenever every value is negative.
• M15. “Validation proves the data is correct.” Correct Validation proves the data obeys the stated rules. A pupil aged 15 who types 13 passes every check you could write.
• M16. “Verification proves the data is sensible.” Correct Verification proves the data matches its source. A verified entry can still break every rule the system has.
• M17. “A check digit detects every error.” Correct It detects most single-digit and transposition errors, but not all of them. The worked example in section 7.4 A shows a single mistyped digit producing the same check digit and being accepted; two errors that cancel each other out can do the same.
• M18. “Normal data means any valid value, including the limits.” Correct Normal data is valid, typical data. The limits themselves have their own name — extreme data — and a test plan should show both.
• M19. “Extreme data means an extremely large invalid value.” Correct Extreme data is the largest or smallest acceptable value, so it is always accepted. A huge invalid number is abnormal data.
• M20. “Boundary data contains only accepted values.” Correct Boundary data is the largest or smallest acceptable value together with the corresponding rejected value on the other side of the limit. It always contains one of each.
• M21. “A dry run means working out what the final answer should be, and a trace table records only the final values.” Correct A dry run follows the algorithm one executed statement at a time, and a trace table records every change, every condition result, every prompt and every output along the way. Why it matters Trace-table questions almost always use a defective algorithm. Writing down the answer you expected is exactly how the fault is missed.

• Read the last row again. “Precision is required” is printed in the syllabus itself, with an example. An answer that says “check if the number is bigger than the other one” is not a wrong idea — it is an unmarked one. The whole of Topic 7 rewards writing the condition, the assignment or the loop bound exactly.
• Which one will the exam ask for? Read the command. “Draw a flowchart” means shapes and arrows. “Write an algorithm”, “write pseudocode” or “complete the pseudocode” means Cambridge pseudocode. “Complete the structure diagram” means fill in boxes in a hierarchy. Answering in the wrong notation is one of the few ways to write a completely correct solution and score zero.
• Check the loop count before you check anything else. A flowchart that inputs five values but tests Count >= 5 instead of Count > 5 reads only four. The fastest way to be certain is to trace the first and the last iteration by hand: what is Count when the first score is read, and what is it when the loop is left? Here the answers are 1 and 6, which is five readings.
• On arrays, decide the lower bound once and say so. Cambridge good practice is to state the bounds explicitly — DECLARE Marks : ARRAY[1:8] OF INTEGER — and this chapter uses a first index of 1 everywhere. What loses marks is starting a loop at 1 and then indexing as though the array began at 0, or changing the convention halfway through one answer. Pick one, write it in the declaration, and hold it.
• Where the decision sits tells you which loop to write. A decision at the bottom of the loop, reached after the body has run, becomes REPEAT … UNTIL <exit condition>. A decision at the top, reached before the body, becomes WHILE <continue condition> DO … ENDWHILE — and note that the condition flips: the flowchart’s exit test becomes the WHILE loop’s continue test. When the number of repetitions is fixed and known, either can be replaced by FOR Count ← 1 TO 5.
• Counting comparisons. If the value is at position n, a linear search makes n comparisons. If it is not present at all, it makes as many comparisons as there are items. Those two sentences answer almost every “how many comparisons” question in this topic, and they also explain why a linear search over a large list is slow in the worst case.
• Say which check, and say what happens when it fails. “Validate the age” is not an answer. “A range check: reject any age below 11 or above 16, display an error message and ask again” names the check, states the rule and describes the consequence — which is usually three separate marking points.
• Four columns, every time. A test-data answer that scores fully gives the value, the category, the expected outcome and the reason. Writing “10, 11, 16, 17” on its own gives a marker four numbers and no evidence that you know why they were chosen. Writing “17 — boundary — rejected — the smallest value above the upper limit, so it proves the algorithm uses <= and not <” gives them everything.
• “It is a syntax error” is almost never the answer. The algorithms set in this topic are logically defective, not unwritable. Marks come from saying what the algorithm does wrong: “the total is reset each time, so only the last score is added” earns; “there is a mistake on line 2” does not. If you can state the wrong output that the fault produces, you have the explanation mark.
• The six-point check before you write anything. (1) What are the inputs, and how many? (2) What is the output, and is it one value or several? (3) Do I need to repeat something, and is the number of repetitions known in advance? (4) Does anything need initialising before the loop? (5) Does anything need to happen only after the loop? (6) What must the algorithm do with data it should not accept? Answer those six and the structure of the algorithm is already decided.