YOUR TOPIC 7 REVISION ROUTE
This is a large topic, so revise in focused sessions rather than trying to memorise every algorithm in one sitting. First understand what a solution must do; then explain how its instructions achieve that behaviour; finally trace and test it.
Choose a section below. Read a worked example, cover the answer and recreate its reasoning in your exercise book. Use the separate Flashcards tab for recall and select uncertain cards to build a personal revision list.
The numbering follows this course’s subdivisions of Topic 7. For extended learning, use the lesson links beside the cards.
7.1 | ANALYSIS AND THE DEVELOPMENT CYCLE
Analysis establishes the problem and requirements before choosing a solution. For a club booking system, “make bookings easier” is a broad aim. “Reject a booking when capacity is reached” is a requirement that can be checked.
Abstraction keeps details relevant to the problem and removes unnecessary detail. A booking model might need a student ID and remaining places, but not a student’s shoe size. Decomposition breaks the problem into smaller jobs, such as receiving a request, checking eligibility and recording a booking.
| Stage | Question to ask |
|---|---|
| Analysis | What must the solution achieve? |
| Design | Which data, steps and structures will meet the requirements? |
| Coding | How will the design be implemented? |
| Testing | Does the observed behaviour meet the requirements? |
Iterative testing means testing and improving during development, not waiting until everything is finished. A failed capacity test may reveal an incorrect comparison, while a missing requirement may require a design change.
7.2 | SYSTEMS, DECOMPOSITION AND DESIGN TOOLS
A system consists of related parts working towards a purpose. A school library can contain loan, return and catalogue subsystems. Each can be decomposed further. Identify inputs, processes, outputs and storage for the relevant boundary: returning a book needs its identifier, a record update and a confirmation.
Working variables hold values during processing. Persistent storage retains information for later use. A running total does not imply a database requirement.
| Representation | Shows | Avoid confusing it with |
|---|---|---|
| Structure diagram | Hierarchy of a problem and its component tasks | The execution order or decision branches |
| Flowchart | Instruction flow using symbols and arrows | A list of unrelated boxes |
| Pseudocode | Precise algorithm instructions in a readable notation | Vague instructions such as check the data |
Common flowchart symbols are a terminator for start/end, rectangle for a process, parallelogram for input/output and diamond for a decision. Arrows show flow. Label decision branches and check where they rejoin.
7.2 | PSEUDOCODE ESSENTIALS
A declaration gives a variable a name and type; it does not assign a useful starting value. Assignment changes a value. In Total ← Total + Amount, evaluate the old Total plus Amount, then store the result back in Total.
DECLARE Total : INTEGER Total ← 0 INPUT Amount Total ← Total + Amount OUTPUT "Total: ", Total
In this short fragment, assume Amount is already declared appropriately. Quoted text is literal output; an unquoted variable name outputs its current value. Use INTEGER for whole-number counts, REAL when fractional values are needed, STRING for text and BOOLEAN for true/false states.
| Construct | Behaviour | Check carefully |
|---|---|---|
| IF / ELSE / ENDIF | Select a branch from a condition | The common code after ENDIF still runs |
| FOR ... TO ... / NEXT | Count-controlled repetition; stated endpoints included | Initial and final bounds |
| WHILE ... DO / ENDWHILE | Continue while condition is true; check before body | Can execute zero times |
| REPEAT / UNTIL | Execute body, then stop when condition is true | Executes at least once |
AND requires both conditions to be true; OR requires at least one; NOT reverses a Boolean value. For inclusive range zero to thirty, use Value >= 0 AND Value <= 30. OR would accept values outside this range.
7.3 | EXPLAIN PURPOSE AND PROCESSES
The purpose is the overall job; the processes are how the algorithm does it. “Calculate average attendance” states purpose. “Initialise a total, add each accepted attendance and divide by the number counted” describes processes.
Reading code line by line without summarising the job does not fully explain its purpose. Equally, naming the job alone omits the important method.
Total ← 0
FOR Index ← 1 TO 3
INPUT Value
Total ← Total + Value
NEXT Index
Average ← Total / 3
OUTPUT AverageAssuming suitable declarations and valid numeric inputs, this receives three values and outputs their mean. With four, seven and one, Total progresses through four, eleven and twelve; Average is four. The FOR repeats input and accumulation, while the division happens once after the loop.
7.4 | LINEAR SEARCH
Linear search examines items in sequence. It works on unsorted data because it does not rely on order. A first-match version stops when it finds the target or exhausts the items.
Position ← 1
Found ← FALSE
WHILE Position <= ItemCount AND NOT Found DO
IF Items[Position] = Target
THEN
Found ← TRUE
MatchIndex ← Position
ELSE
Position ← Position + 1
ENDIF
ENDWHILEThis fragment assumes a declared array indexed from one, suitable variables and an initial MatchIndex sentinel such as zero. The bound check protects access inside the body; Found prevents further searching after a match.
| Items | Target | Items compared | Result |
|---|---|---|---|
| S104, S307, S205, S412, S118 | S205 | S104, S307, S205 | Found at index 3 |
| Same five items | S999 | All five | Not found |
The first item takes one comparison. A missing item requires checking every item. If duplicates exist, this version finds the first matching position, not every match.
7.4 | BUBBLE SORT ACROSS MULTIPLE PASSES
Bubble sort compares adjacent values and swaps them when they are in the wrong order. In ascending order, a larger left value swaps with a smaller right value. Values move through repeated neighbouring comparisons.
| Pass | After comparison 1 | After comparison 2 | After comparison 3 | Swaps |
|---|---|---|---|---|
| Start | 5, 2, 4, 1 | |||
| 1 | 2, 5, 4, 1 | 2, 4, 5, 1 | 2, 4, 1, 5 | 3 |
| 2 | 2, 4, 1, 5 | 2, 1, 4, 5 | 2, 1, 4, 5 | 1 |
| 3 | 1, 2, 4, 5 | 1, 2, 4, 5 | 1, 2, 4, 5 | 1 |
| 4 | 1, 2, 4, 5 | 1, 2, 4, 5 | 1, 2, 4, 5 | 0 |
After pass one, five is in its final position, but the remaining values are not sorted. A complete pass with no swaps establishes that this version can stop. Here it uses twelve comparisons and five swaps. Other correct versions shorten later passes, so their comparison counts differ.
Temp ← Values[Index] Values[Index] ← Values[Index + 1] Values[Index + 1] ← Temp
Temp preserves the old left value. Without it, overwriting the left value first can lose data and duplicate the right value. Revisit the interactive comparison-by-comparison sort.
7.4 | TOTALS, COUNTS, MAXIMUM, MINIMUM AND MEAN
A total adds values; a count adds one per item meeting a rule. For values four, five, eight, two and five, values at least five have total eighteen and count three. Their mean is six, not eighteen divided by all five inputs.
IF Value >= 5
THEN
Total ← Total + Value
Count ← Count + 1
ENDIFInitialise both before repetition. When calculating a conditional mean, check Count is positive before division. If no item qualifies, provide an appropriate alternative.
For extrema, initialise Maximum and Minimum from the first actual value when at least one input is guaranteed. Starting Maximum at zero fails for all-negative inputs.
| Next value | Total | Maximum | Minimum |
|---|---|---|---|
| First: -3 | -3 | -3 | -3 |
| 6 | 3 | 6 | -3 |
| -7 | -4 | 6 | -7 |
| 2 | -2 | 6 | -7 |
| 2 | 0 | 6 | -7 |
Only update Maximum when a new value is greater, and Minimum when it is smaller. Adding an input to Total does not automatically update either extremum.
7.5 | VALIDATION CHECKS
Validation checks whether data meets specified rules. It does not establish that a plausible value is true. A mark of thirty-four can pass a zero-to-fifty range while still being different from the mark on a paper record.
| Check | Purpose | Example |
|---|---|---|
| Range | Within stated numerical limits | 0 <= Mark <= 50 |
| Length | Required number of characters | Identifier contains six characters |
| Type | Appropriate data type | Whole-number quantity |
| Presence | Required data supplied | Name not empty |
| Format | Required arrangement or pattern | Two uppercase letters followed by four digits |
| Check digit | Detect certain errors using a calculated digit | Recalculate from the other digits and compare |
For example, a date can follow a day/month/year pattern yet describe a nonexistent date. A numeric-looking identifier may need STRING storage to retain leading zeros. Presence of text does not automatically exclude a spaces-only value unless that rule is implemented.
Handle checks in a sensible order. Perform type or format handling before arithmetic that assumes numeric values. If a question assumes whole-number input, state that assumption rather than inventing an unsupported conversion instruction.
7.5 | CHECK DIGITS AND THEIR LIMITS
Use the calculation specified in the question. A check-digit scheme detects some errors; passing it is not proof of a correct source value. Do not assume a familiar barcode formula applies to every example.
In an illustrative scheme, multiply four payload digits by weights one, three, one, three. Choose a final digit making the complete sum a multiple of ten.
| Payload | Weighted sum | Check digit | Complete code |
|---|---|---|---|
| 4826 | 4 + 24 + 2 + 18 = 48 | 2 | 48262 |
| 0526 | 0 + 15 + 2 + 18 = 35 | 5 | 05265 |
Changing 48262 to 48362 produces total fifty-one including the check digit, so it is rejected. However, transposing 05265 to 50265 produces weighted sum twenty-five plus five, or thirty, so this error passes. Detection depends on the scheme.
7.5 | VERIFICATION AND THE COMPARISON
Verification checks whether data has been copied accurately. A visual check compares entered data with the original source. Double entry enters data twice and compares the entries, requesting correction if they differ.
| Situation | Relevant check | What it establishes |
|---|---|---|
| Entered mark 43, source mark 34 | Visual verification | The entered value differs from the source |
| Entries AB1042 and AB1402 | Double entry | The two entries disagree |
| Entered mark 43, permitted range 0 to 50 | Range validation | The value is within the permitted range |
Double entry is useful when entries are made independently. Copying the first entry into the second defeats that purpose. Both entries could still contain the same mistake, and visual checks can miss errors.
Validation and verification complement each other. Neither guarantees that the original source is true, and matching empty entries do not replace a required presence check.
7.6 | CHOOSE TEST DATA FOR A REASON
Normal data is valid data expected to be accepted. Abnormal data is invalid data expected to be rejected. A correctly rejected invalid input is a passed test, not a failed test.
For Cambridge terminology, extreme data uses the accepted minimum and maximum. Boundary testing includes the accepted endpoints and the nearest rejected values outside them, with the unit or precision specified.
| Range: whole numbers 0 to 50 | Values | Expected behaviour |
|---|---|---|
| Normal representative | 34 | Accept |
| Abnormal example | 500 | Reject |
| Extreme | 0, 50 | Accept both |
| Boundary | -1, 0, 50, 51 | Reject, accept, accept, reject |
For an exclusive whole-number rule greater than twelve and less than eighteen, accepted extremes are thirteen and seventeen. Boundary values are twelve, thirteen, seventeen and eighteen. For continuous real values there is no universal nearest neighbour; state a precision such as one decimal place.
7.6 | WRITE A USEFUL TEST PLAN
Expected results come from the requirements before the test. Actual results come from observing an implementation. Keep them separate; do not label predictions as observations.
| Test | Data / initial state | Expected result | Actual result |
|---|---|---|---|
| Lower bound | Mark 0; range 0 to 50 | Accept and store 0 | Not run |
| Below lower bound | Mark -1 | Reject; request replacement; do not store -1 | Not run |
| Upper bound | Mark 50 | Accept and store 50 | Not run |
| Above upper bound | Mark 51 | Reject; request replacement; do not store 51 | Not run |
Include state where it affects behaviour, such as an existing booking or remaining capacity. Reset state for independent tests, or explicitly describe an intended sequence.
Compare all required effects, not just the visible message. A system might display “rejected” but still store the invalid value. After fixing a fault, retest it and check relevant retained behaviour.
7.7 | TRACE TABLES: FOLLOW THE INSTRUCTIONS
A dry run follows an algorithm by hand. A trace table records its state as instructions execute. Read the given code rather than silently correcting it to what you think it should do.
Assignment uses the current right-hand-side values. An OUTPUT prompt is an output event; a user’s response is an input event. Show a declaration as not yet assigned until a value is actually supplied.
Total ← 0
Count ← 0
FOR Index ← 1 TO 4
OUTPUT "Enter score"
INPUT Score
IF Score >= 5
THEN
Total ← Total + Score
Count ← Count + 1
ENDIF
NEXT Index
OUTPUT Total, Count| Index | Score input | Score >= 5? | Total after iteration | Count after iteration |
|---|---|---|---|---|
| 1 | 4 | False | 0 | 0 |
| 2 | 5 | True | 5 | 1 |
| 3 | 8 | True | 13 | 2 |
| 4 | 2 | False | 13 | 2 |
This table records the state after each iteration. An exam table may require each assignment or only changed values instead; follow its layout and make your convention clear. Do not infer an unspecified post-loop FOR variable value.
7.7 | WHILE AND REPEAT STOP IN DIFFERENT WAYS
WHILE checks before the body and continues when true. REPEAT checks after the body and stops when true. The corresponding conditions often point in opposite directions.
Count ← 1
WHILE Count <= 3 DO
OUTPUT Count
Count ← Count + 1
ENDWHILEThis outputs one, two, three. Count then becomes four; the condition is false and the loop exits. Starting at four would output nothing.
Count ← 1
REPEAT
OUTPUT Count
Count ← Count + 1
UNTIL Count > 3This also outputs one, two, three when starting at one. But starting at four outputs four once before Count becomes five and the stop condition is checked.
In nested loops, finishing an inner retry does not finish the outer loop. Track which loop controls accepted items and which handles replacement attempts.
7.8 | IDENTIFY, EXPLAIN AND CORRECT ERRORS
Explain an error through its effect, then give a precise correction. “The loop is wrong” does not identify whether the problem is its bound, update or stopping condition.
| Fault | Effect | Correction |
|---|---|---|
| Total reset inside input loop | Earlier values lost | Initialise once before the loop |
| Count ← Count + Value | Sums values instead of counting | Add 1 per qualifying item |
| Value >= 0 OR Value <= 30 | Out-of-range values accepted | Use AND |
| WHILE loop without progress update | May repeat forever | Update the controlling state as required |
| Maximum initialised to zero | Fails on all-negative values | Start from first actual input |
| Average calculated before zero check | Possible division by zero | Guard division first |
| Search uses Position < ItemCount | May omit final item | Include final valid index |
A syntax error concerns the notation or grammar. A logic error can be syntactically valid but give the wrong result. An execution problem can arise from an invalid operation such as division by zero. Use a focused input that exposes the specific fault, then check the corrected algorithm.
7.9 | BUILD A SOLUTION FROM A SCENARIO
Break the paragraph into requirements before choosing keywords. Identify repeated inputs, valid ranges, calculations, decisions and final outputs. Then choose variables for clear jobs and decompose the processing.
Receive attendance for three classes. Each whole-number entry must be from zero to thirty inclusive, retrying values outside that range. Output total attendance and Large session if it is at least sixty, otherwise Small session. Assume whole-number input.
Total ← 0
FOR ClassIndex ← 1 TO 3
REPEAT
OUTPUT "Enter attendance from 0 to 30"
INPUT Attendance
UNTIL Attendance >= 0 AND Attendance <= 30
Total ← Total + Attendance
NEXT ClassIndex
OUTPUT "Total attendance: ", Total
IF Total >= 60
THEN
OUTPUT "Large session"
ELSE
OUTPUT "Small session"
ENDIFAssume Attendance, Total and ClassIndex are declared INTEGER. The outer loop controls three accepted class values. The inner loop retries for the current class. Total updates only after acceptance; classification happens after all classes.
Attempts twelve, thirty-one, eighteen and thirty give three accepted values twelve, eighteen and thirty. Total is sixty and the message is Large session. Four attempts do not mean four classes.
7.9 | AMEND A COMPLETE ALGORITHM
Suppose the task changes to four classes, with an extra count of participating classes whose attendance is positive, and a mean per participating class. Keep the original validation, total and classification. If none participates, output an alternative instead of dividing.
| Change | Where it belongs |
|---|---|
| FOR upper limit becomes 4 | Outer header |
| ParticipatingClasses ← 0 | Before FOR |
| If Attendance > 0, add 1 to count | After accepted input, inside FOR |
| Average ← Total / ParticipatingClasses | After FOR, only when count > 0 |
| No participating classes message | Alternative branch when count is zero |
For zero, twelve, zero and eighteen, Total is thirty, count two and mean fifteen. Dividing by four answers a different question. Four zeros exercise the no-participation branch while the retained classification still gives Small session.
Regression testing checks retained rules after an amendment. Adapt old tests where the requirement intentionally changed: a three-input test now needs a fourth accepted input. Keep checking accepted endpoints, rejected attempts and the inclusive sixty threshold.
COMMON MISTAKES | USE THESE AS YOUR FINAL CHECK
- Confusing a structure diagram’s hierarchy with a flowchart’s execution order.
- Declaring a variable but forgetting to initialise a running total or count.
- Adding a value when you meant to count one item.
- Tracing the intended algorithm instead of the algorithm actually given.
- Treating REPEAT UNTIL as a continue-while condition.
- Assuming one bubble-sort pass sorts the whole list.
- Claiming validation guarantees accurate or true data.
- Using extreme to mean a very large invalid value in Cambridge test-data terminology.
- Ignoring prompts, rejected attempts or required storage effects.
- Checking only the changed line after amending a complete solution.
WRITTEN ANSWERS | MAKE YOUR REASONING VISIBLE
Describe gives characteristics or main points. Explain makes reasons or relationships clear. Compare identifies similarities and/or differences. Calculate works out a result from the supplied information. Suggest applies knowledge to a situation with possible valid responses.
For an explanation, link cause and effect: “Accumulation follows validation because an invalid attempt must not enter the total, therefore the retry does not distort the final result.” Use connectives when they express a real relationship, rather than merely adding words.
Practise: explain why a zero guard is needed; compare validation and verification; describe how one bubble-sort pass works; calculate a trace’s final values; suggest boundary tests for a stated range.
YOUR THREE-SESSION REVISION PLAN
Session one: development, design tools and standard algorithms. Recreate a search, swap and conditional total without looking.
Session two: validation, verification and testing. Choose data for specific faults, including endpoint mistakes, and state expected outcomes.
Session three: traces, corrections and scenario solutions. Follow a nested retry, correct a complete algorithm and explain the placement of each amendment.
Return to selected weak cards between sessions. When ready, use the end-of-topic review to check your understanding across the whole topic.
End of topic review