Identify errors in given algorithms and suggest ways of correcting them

Algorithm Design, Problem‑Solving & Computer Systems (Cambridge IGCSE Computer Science 0478)

Learning Objectives

• Identify and classify syntax, logical, boundary/edge‑case, non‑termination and efficiency errors in algorithms.
• Explain why each error occurs and how it affects the result or termination.
• Apply a systematic, exam‑style procedure to trace, test and correct algorithms (pseudocode or flowcharts).
• Link algorithm design to the programming concepts required for Paper 2 (variables, selection, iteration, arrays, file handling).
• Demonstrate awareness of validation/verification, test‑data selection and the standard solution methods listed in the syllabus.
• Recall key computer‑systems concepts (data representation, hardware, software, networks, emerging technologies) and use them in exam questions.

Mapping to the Cambridge Syllabus (Topic 7) – What the Notes Cover & What Is Added

Syllabus Sub‑point	Current coverage	Additional depth / new content
7.1 – Algorithms and flowcharts	Notation reminder, flowchart symbols, step‑by‑step error‑finding.	Common flow‑chart mistakes (missing start/end, wrong connector direction, overlapping arrows). Mini‑exercise: spot the error in a 6‑step flowchart.
7.2 – Validation and verification checks	Validation steps added to every example (range, type, presence).	Checklist of typical checks (range, length, format, check‑digit, uniqueness). Example: validate a UK post‑code.
7.3 – Test data selection and trace tables	Procedure includes “trace with a simple test case” and a separate “Trace‑table example”.	Guidelines for choosing normal, boundary and error‑inducing data. Full trace‑table template with colour‑coded “expected vs. actual”.
7.4 – Standard solution methods (search, sort, totalling, counting, max/min/average)	Dedicated “Standard methods” box with short pseudocode for each.	Time‑ and space‑complexity notes (O(n), O(n²), O(1) etc.). When to prefer linear search vs. binary search.
7.5 – Error‑finding in pseudocode and flowcharts	Comprehensive error categories, systematic procedure, practice questions.	Side‑by‑side “incorrect vs. correct” flowchart examples. Quick‑reference list of common syntax traps.
7.6 – Efficiency (time & space)	Efficiency‑error column, complexity comparison table.	Explicit introduction to Big‑O notation, examples of O(n), O(n log n) and O(n²). Decision‑tree for choosing a more efficient method.
7.7 – Algorithm documentation (comments, line numbers)	Notation reminder includes comment style and line‑numbering.	Sample comment block (purpose, inputs, outputs, assumptions). Guidelines for concise but complete documentation.
7.8 – Converting between pseudocode and flowcharts	Notation reminder shows both symbols and equivalent pseudocode.	Mini‑exercise: convert a 5‑step algorithm to a flowchart and back.
7.9 – Using appropriate data types and structures	Programming sidebar introduces variables, arrays, basic file I/O.	Notes on choosing integer vs. real, 1‑D vs. 2‑D arrays, and when to use a file versus an array. Example of a 2‑D array for a pixel image.

1 – Computer Systems (Syllabus 1‑6)

1.1 Data Representation

• Binary, octal, decimal and hexadecimal – conversion methods, significance of each position.
• Signed integers – two’s‑complement representation.
• Real numbers – fixed‑point vs. floating‑point basics.
• Characters – ASCII/Unicode tables (example: ‘A’ = 65₁₀ = 41₁₆).
• Images, sound & video – pixel, colour depth, sampling rate, compression (lossy vs. loss‑less).

1.2 Data Transmission

• Analogue vs. digital signals.
• Baud, bit‑rate, bandwidth.
• Serial & parallel transmission, synchronous vs. asynchronous.
• Error‑detection methods – parity bit (even/odd), checksum, CRC (conceptual).

1.3 Hardware

• CPU: control unit, ALU, registers, clock speed.
• Primary storage – RAM (volatile), ROM (non‑volatile), cache.
• Secondary storage – magnetic (HDD), solid‑state (SSD), optical (CD/DVD), flash (USB).
• Input devices (keyboard, mouse, scanner, microphone) and output devices (monitor, printer, speaker).

1.4 Software

• System software – operating system (tasks, memory management, file system).
• Application software – examples (word processor, spreadsheet, web browser).
• Utility software – antivirus, backup, compression tools.

1.5 Networks & the Internet

• Network topologies – star, bus, ring, mesh.
• LAN vs. WAN, client‑server vs. peer‑to‑peer.
• IP addressing (IPv4), subnet mask, NAT.
• MAC address, Ethernet frame structure.
• Common protocols – HTTP, HTTPS, FTP, SMTP, TCP, UDP.
• Cyber‑security basics – firewalls, encryption (symmetric vs. asymmetric), authentication.

1.6 Emerging Technologies

• Artificial intelligence – machine learning basics, example: image classification.
• Robotics – sensors, actuators, control algorithms.
• Internet of Things (IoT) – embedded devices, data collection.
• Digital currencies – blockchain concept, public vs. private keys.

Quick‑Reference Table – Units & Conversions

Unit	Symbol	1 KB =	1 Mb =
bit	b	‑	1 000 bits
byte	B	8 bits	‑
kilobyte	KB	1 024 bytes	‑
kilobit	Kb	‑	1 024 bits
megabyte	MB	1 024 KB	‑
megabit	Mb	‑	1 024 Kb

2 – Notation Reminder (Cambridge Pseudocode & Flowchart Symbols)

3 – Common Types of Errors

Error Category	Description	Typical Symptoms
Syntax Errors	Violations of the pseudocode language rules (missing ←, wrong keyword case, unmatched END… statements).	Examiner marks “cannot be interpreted”; program will not run.
Logical Errors	Algorithm runs but yields wrong results for one or more test cases.	Incorrect output, off‑by‑one, wrong calculation.
Boundary / Edge‑case Errors	Failure when the input is the smallest, largest, zero, negative or otherwise special value.	Crash, wrong answer, infinite loop for n = 0, n = 1, etc.
Infinite Loops / Non‑termination	Loop condition never becomes false, often due to missing update or wrong relational operator.	Program never reaches END, memory exhaustion.
Efficiency Errors	Choosing an algorithm with unnecessary time or space consumption.	Execution time grows faster than required (e.g., O(n²) when O(n) is possible).
Validation / Verification Errors	Missing or incorrect checks on input type, range, length, format or check‑digit.	Invalid data accepted → later crashes or wrong results.

4 – Step‑by‑Step Error‑Finding Procedure (Exam‑style)

1. State the purpose – Write a one‑sentence comment describing the intended outcome.
2. List inputs, outputs and assumptions – Include data types, allowed ranges and any pre‑conditions.
3. Validate inputs – Insert checks for type, range, length, format, uniqueness, or check‑digit.
4. Select test data
   • Normal case (typical values).
   • Boundary cases (minimum, maximum, zero, one).
   • Error‑inducing case (negative where not allowed, non‑numeric input, duplicate values).
5. Trace with a trace table – Columns for each variable, rows for each executed line. Highlight the row where the error becomes visible.
6. Examine each statement
   • Variable names are consistent and correctly initialised.
   • Loop start, end and increment values cover the required range.
   • Decision expressions are mutually exclusive and exhaustive.
   • Assignments use the ← symbol; arithmetic operators are correct.
7. Check termination – Ensure every loop or recursion moves toward a clear terminating condition.
8. Assess efficiency
   • Identify the algorithmic class (O(1), O(n), O(n log n), O(n²)…).
   • Compare with the standard methods in the syllabus – could a more efficient method be used?
9. Document the correction – Rewrite the faulty lines, add concise comments, and update the flowchart if required.

5 – Standard Solution Methods (Topic 7.4)

• Linear search – O(n) time, O(1) space.
  

  01 READ n
  02 DECLARE a[1..n] OF INTEGER
  03 FOR i ← 1 TO n
  04     READ a[i]
  05 ENDFOR
  06 READ key
  07 SET pos ← 0
  08 FOR i ← 1 TO n
  09     IF a[i] = key THEN
  10         SET pos ← i
  11         STOP               // first occurrence
  12     ENDIF
  13 ENDFOR
  14 IF pos = 0 THEN
  15     PRINT "Not found"
  16 ELSE
  17     PRINT "Position = " + pos
  18 ENDIF
          

• Binary search (sorted array) – O(log n) time, O(1) space.
  

  01 READ n
  02 DECLARE a[1..n] OF INTEGER
  03 FOR i ← 1 TO n
  04     READ a[i]
  05 ENDFOR
  06 READ key
  07 SET low ← 1
  08 SET high ← n
  09 SET pos ← 0
  10 WHILE low ≤ high
  11     SET mid ← (low + high) DIV 2
  12     IF a[mid] = key THEN
  13         SET pos ← mid
  14         STOP
  15     ELSEIF a[mid] < key THEN
  16         SET low ← mid + 1
  17     ELSE
  18         SET high ← mid - 1
  19     ENDIF
  20 ENDWHILE
  21 IF pos = 0 THEN
  22     PRINT "Not found"
  23 ELSE
  24     PRINT "Position = " + pos
  25 ENDIF
          

• Bubble sort – O(n²) time, O(1) space (simple, exam‑friendly).
  

  01 READ n
  02 DECLARE a[1..n] OF INTEGER
  03 FOR i ← 1 TO n
  04     READ a[i]
  05 ENDFOR
  06 FOR pass ← 1 TO n-1
  07     FOR i ← 1 TO n-pass
  08         IF a[i] > a[i+1] THEN
  09             SET temp ← a[i]
  10             SET a[i] ← a[i+1]
  11             SET a[i+1] ← temp
  12         ENDIF
  13     ENDFOR
  14 ENDFOR
  15 // a is now sorted
          

• Selection sort (more efficient than bubble for teaching) – O(n²) time, O(1) space.
  

  01 READ n
  02 DECLARE a[1..n] OF INTEGER
  03 FOR i ← 1 TO n
  04     READ a[i]
  05 ENDFOR
  06 FOR i ← 1 TO n-1
  07     SET minIdx ← i
  08     FOR j ← i+1 TO n
  09         IF a[j] < a[minIdx] THEN
  10             SET minIdx ← j
  11         ENDIF
  12     ENDFOR
  13     IF minIdx ≠ i THEN
  14         SET temp ← a[i]
  15         SET a[i] ← a[minIdx]
  16         SET a[minIdx] ← temp
  17     ENDIF
  18 ENDFOR
          

• Totalling / averaging – O(n) time, O(1) space.
  

  01 READ n
  02 SET sum ← 0
  03 FOR i ← 1 TO n
  04     READ x
  05     SET sum ← sum + x
  06 ENDFOR
  07 IF n > 0 THEN
  08     SET avg ← sum / n
  09     PRINT "Sum = " + sum
  10     PRINT "Average = " + avg
  11 ELSE
  12     PRINT "No data entered"
  13 ENDIF
          

• Counting occurrences – O(n) time, O(1) space (counter variable).
  

  01 READ n, target
  02 SET count ← 0
  03 FOR i ← 1 TO n
  04     READ x
  05     IF x = target THEN
  06         SET count ← count + 1
  07     ENDIF
  08 ENDFOR
  09 PRINT "Occurrences of " + target + " = " + count
          

• Maximum / minimum – O(n) time, O(1) space.
  

  01 READ n
  02 READ max          // first value becomes initial maximum
  03 FOR i ← 2 TO n
  04     READ x
  05     IF x > max THEN
  06         SET max ← x
  07     ENDIF
  08 ENDFOR
  09 PRINT "Maximum = " + max
          

6 – Illustrative Example 1 – Finding the Maximum Value

Faulty pseudocode

01 READ n
02 SET max ← 0
03 FOR i ← 1 TO n
04     READ x
05     IF x > max THEN
06         SET max ← x
07     ENDIF
08 ENDFOR
09 PRINT max

Errors Identified

• Initialisation error: max ← 0 fails when all inputs are negative.
• Boundary error: No handling of n ≤ 0 – loop never runs, leaving max at 0.
• Missing validation: No check that each entered number lies within the expected range.

Corrected Cambridge‑style pseudocode

01 READ n
02 // Validation of n (must be positive)
03 IF n ≤ 0 THEN
04     PRINT "No numbers to compare"
05     STOP
06 ENDIF
07 READ max               // first data value becomes the initial maximum
08 FOR i ← 2 TO n
09     READ x
10     // Optional: validate x here (e.g., range check)
11     IF x > max THEN
12         SET max ← x
13     ENDIF
14 ENDFOR
15 PRINT "Maximum = " + max

Why the Corrections Work

1. Lines 3‑6 guard against an empty data set, preventing a meaningless output.
2. Line 7 reads the first real value, guaranteeing a legitimate initial maximum even if it is negative.
3. The loop now starts at 2 because the first value has already been stored.
4. All keywords are uppercase; assignment uses the left‑arrow; comments explain each step.

7 – Illustrative Example 2 – Computing the Factorial

Faulty pseudocode

01 READ n
02 SET fact ← 1
03 FOR i ← 1 TO n
04     SET fact ← fact * i
05 ENDFOR
06 PRINT fact

Errors Identified

• No handling of negative n (factorial undefined).
• Loop starts at 1 – the first multiplication is unnecessary.
• Potential overflow for large n (note for discussion).

Corrected pseudocode

01 READ n
02 // Validation of n
03 IF n < 0 THEN
04     PRINT "Factorial not defined for negative numbers"
05     STOP
06 ENDIF
07 SET fact ← 1
08 FOR i ← 2 TO n
09     SET fact ← fact * i
10 ENDFOR
11 PRINT "Factorial = " + fact

Explanation

1. Lines 3‑6 reject invalid input, satisfying the validation requirement.
2. The loop now starts at 2, saving one unnecessary iteration.
3. Comments clarify purpose and validation steps.

8 – Illustrative Example 3 – Collatz (3n + 1) Loop – Infinite‑Loop Risk

Faulty pseudocode

01 READ x
02 WHILE x != 0
03     IF x % 2 = 0 THEN
04         SET x ← x / 2
05     ELSE
06         SET x ← 3 * x + 1
07     ENDIF
08 ENDWHILE
09 PRINT "Done"

Problem

• If x is negative, the sequence never reaches 0 (it diverges), causing a non‑terminating loop.

Corrected version with validation

01 READ x
02 // Validation – only positive integers are allowed
03 IF x ≤ 0 THEN
04     PRINT "Input must be a positive integer"
05     STOP
06 ENDIF
07 WHILE x ≠ 1
08     IF x % 2 = 0 THEN
09         SET x ← x / 2
10     ELSE
11         SET x ← 3 * x + 1
12     ENDIF
13 ENDWHILE
14 PRINT "Sequence reached 1 – Done"

Key Points

• Validation (lines 3‑6) eliminates the infinite‑loop scenario.
• The loop condition is changed to x ≠ 1, matching the standard Collatz definition (the sequence always terminates at 1 for positive integers).
• All arithmetic operators and comparison symbols follow Cambridge conventions.

9 – Efficiency – Big‑O Overview (Syllabus 7.6)

Complexity	Typical example (Cambridge)	When to use
O(1)	Access a single array element, simple arithmetic.	When the operation does not depend on input size.
O(n)	Linear search, totalling, counting.	Best choice for a single pass over data.
O(log n)	Binary search (sorted array).	When data are sorted and many look‑ups are required.
O(n log n)	Merge sort, quick sort.	Preferred for large data sets where sorting is needed.
O(n²)	Bubble sort, selection sort, nested loops over the same data.	Acceptable for small n (e.g., n ≤ 20) in exam questions.

Decision‑tree for choosing a more efficient method

1. Do you need to search a sorted list? → Use binary search (O(log n)) instead of linear.
2. Do you need to sort a large list (n > 30)? → Use merge/quick sort (O(n log n)) rather than bubble/selection.
3. Is the problem a simple count/totalling task? → Use a single loop (O(n)) and avoid nested loops.
4. Can you replace a nested loop with a mathematical formula? → Yes → O(1) or O(n) solution is possible.

10 – Practice Questions (Error‑Finding)

1. Faulty algorithm – find the average of a list of marks, but the total is printed instead.
   

   01 READ n
   02 SET total ← 0
   03 FOR i ← 1 TO n
   04     READ mark
   05     SET total ← total + mark
   06 ENDFOR
   07 PRINT total
           

   • Identify the error.
   • Correct the algorithm.
   • Provide a trace table for n = 3, marks = 40, 55, 70.
2. Infinite‑loop risk – a program that decrements a counter but uses the wrong relational operator.
   

   01 READ n
   02 WHILE n > 0
   03     PRINT n
   04     // missing decrement
   05 ENDWHILE
           

   • Explain why the loop never terminates.
   • Insert the missing statement and show the corrected loop.
3. Boundary error – algorithm to find the smallest positive integer in an array, but initialises min ← 0.
   

   01 READ n
   02 SET min ← 0
   03 FOR i ← 1 TO n
   04     READ x
   05     IF x > 0 AND x < min THEN
   06         SET min ← x
   07     ENDIF
   08 ENDFOR
   09 PRINT min
           

   • Identify the logical mistake.
   • Rewrite the initialisation and the condition correctly.

11 – Quick‑Reference Checklist for Exam – Error‑Finding

1. Read the question – note purpose, inputs, outputs, constraints.
2. Check line‑by‑line for:
   • Upper‑case keywords?
   • Correct assignment arrow?
   • Consistent variable names?
   • Proper initialisation?
   • Loop bounds and update statements?
   • Decision logic – mutually exclusive and exhaustive?
3. Validate every input (type, range, length, format).
4. Choose three test cases (normal, boundary, error) and trace them.
5. Look for non‑termination – does each loop move toward its exit condition?
6. Assess efficiency – could a standard method give a better Big‑O?
7. Write brief comments explaining each correction.
8. Re‑check the whole algorithm after corrections.