CIE IGCSE | TOPIC 7

ALGORITHM DESIGN AND PROBLEM-SOLVING REVISION

Revisit the whole algorithm-design topic through clear explanations, worked algorithms, trace tables and targeted checks. Select uncertain flashcards to build your revision plan.

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.

Testing can lead back to earlier stages
StageQuestion to ask
AnalysisWhat must the solution achieve?
DesignWhich data, steps and structures will meet the requirements?
CodingHow will the design be implemented?
TestingDoes 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.

Choose the representation requested by the question
RepresentationShowsAvoid confusing it with
Structure diagramHierarchy of a problem and its component tasksThe execution order or decision branches
FlowchartInstruction flow using symbols and arrowsA list of unrelated boxes
PseudocodePrecise algorithm instructions in a readable notationVague 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.

Conditions determine continuation or stopping differently
ConstructBehaviourCheck carefully
IF / ELSE / ENDIFSelect a branch from a conditionThe common code after ENDIF still runs
FOR ... TO ... / NEXTCount-controlled repetition; stated endpoints includedInitial and final bounds
WHILE ... DO / ENDWHILEContinue while condition is true; check before bodyCan execute zero times
REPEAT / UNTILExecute body, then stop when condition is trueExecutes 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 Average

Assuming 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
ENDWHILE

This 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.

Do not report a missing item as index five
ItemsTargetItems comparedResult
S104, S307, S205, S412, S118S205S104, S307, S205Found at index 3
Same five itemsS999All fiveNot 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.

This full-width swap-flag version checks all three pairs on every pass
PassAfter comparison 1After comparison 2After comparison 3Swaps
Start5, 2, 4, 1
12, 5, 4, 12, 4, 5, 12, 4, 1, 53
22, 4, 1, 52, 1, 4, 52, 1, 4, 51
31, 2, 4, 51, 2, 4, 51, 2, 4, 51
41, 2, 4, 51, 2, 4, 51, 2, 4, 50

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
ENDIF

Initialise 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.

Five values: maximum 6, minimum -7, mean 0
Next valueTotalMaximumMinimum
First: -3-3-3-3
636-3
-7-46-7
2-26-7
206-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.

A format check alone does not establish every semantic rule
CheckPurposeExample
RangeWithin stated numerical limits0 <= Mark <= 50
LengthRequired number of charactersIdentifier contains six characters
TypeAppropriate data typeWhole-number quantity
PresenceRequired data suppliedName not empty
FormatRequired arrangement or patternTwo uppercase letters followed by four digits
Check digitDetect certain errors using a calculated digitRecalculate 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.

Illustrative scheme, not a universal real-world standard
PayloadWeighted sumCheck digitComplete code
48264 + 24 + 2 + 18 = 48248262
05260 + 15 + 2 + 18 = 35505265

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.

A value can pass validation and fail verification
SituationRelevant checkWhat it establishes
Entered mark 43, source mark 34Visual verificationThe entered value differs from the source
Entries AB1042 and AB1402Double entryThe two entries disagree
Entered mark 43, permitted range 0 to 50Range validationThe 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.

Extreme values also form part of these boundary tests
Range: whole numbers 0 to 50ValuesExpected behaviour
Normal representative34Accept
Abnormal example500Reject
Extreme0, 50Accept both
Boundary-1, 0, 50, 51Reject, 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.

Planned tests with actual results honestly left unrecorded
TestData / initial stateExpected resultActual result
Lower boundMark 0; range 0 to 50Accept and store 0Not run
Below lower boundMark -1Reject; request replacement; do not store -1Not run
Upper boundMark 50Accept and store 50Not run
Above upper boundMark 51Reject; request replacement; do not store 51Not 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
Assume suitable declarations; prompt appears four times; final outputs 13 and 2
IndexScore inputScore >= 5?Total after iterationCount after iteration
14False00
25True51
38True132
42False132

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
ENDWHILE

This 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 > 3

This 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.

Corrections must match the stated requirements
FaultEffectCorrection
Total reset inside input loopEarlier values lostInitialise once before the loop
Count ← Count + ValueSums values instead of countingAdd 1 per qualifying item
Value >= 0 OR Value <= 30Out-of-range values acceptedUse AND
WHILE loop without progress updateMay repeat foreverUpdate the controlling state as required
Maximum initialised to zeroFails on all-negative valuesStart from first actual input
Average calculated before zero checkPossible division by zeroGuard division first
Search uses Position < ItemCountMay omit final itemInclude 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"
ENDIF

Assume 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.

Assume INTEGER count and REAL Average are declared
ChangeWhere it belongs
FOR upper limit becomes 4Outer header
ParticipatingClasses ← 0Before FOR
If Attendance > 0, add 1 to countAfter accepted input, inside FOR
Average ← Total / ParticipatingClassesAfter FOR, only when count > 0
No participating classes messageAlternative 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