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 for problems of increasing size, in the notation the question asks for — pseudocode, a flowchart, or, in the final Paper 2 scenario question only, program code.

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.

• 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 An algorithm you are asked to trace may be defective — outcome 7.8 is entirely about finding errors in given algorithms. Writing down the answer you expected is exactly how such a fault is missed.

• The routes are study methods, not qualification tiers. “Learn” and “Revise” describe when you read something, never who has to know it. If you are reading this chapter at all, all twelve requirements apply to you.
• 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 — three distinct pieces of information, where the first answer gives only a vague instruction.
• 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.