Understand the need for validation and verification checks

Algorithm Design, Validation & Verification – Cambridge IGCSE 0478

Learning Objectives

• Explain why validation and verification are required when turning an algorithm into a program.
• Identify and apply the full range of checks and tests prescribed by the syllabus (AO1, AO2, AO3).
• Design, document and test algorithms using the standard pseudocode and flow‑chart conventions.
• Describe the key components of a computer system, data representation and emerging technologies.

1. Computer Systems – Core Concepts (Paper 1)

1.1 Data Representation

• Number systems: binary, octal, decimal, hexadecimal – conversion methods and place‑value.
• Two’s‑complement for signed integers.
• ASCII / Unicode – 7‑bit and 8‑bit character codes.
• Images & sound: pixels, colour depth, sampling rate, bit‑rate, compression (lossless vs. lossy).
• Storage units: bit, byte, kilobyte, megabyte, gigabyte, terabyte.
• Error‑detection: parity bits, checksums, CRC.
• Simple encryption: Caesar cipher, substitution – why it is not secure.

1.2 Hardware & Software

Component	Role	Typical Exam Example
CPU (ALU, control unit, registers)	Executes instructions, performs arithmetic/logic.	Explain the fetch‑decode‑execute cycle.
Memory hierarchy	Registers → Cache → RAM → Secondary storage.	Why RAM is faster than a hard‑disk.
I/O devices	Input (keyboard, mouse, scanner) & output (monitor, printer, speaker).	Identify an example of an analogue‑to‑digital converter.
Operating system	Manages resources, provides interface, handles files.	State two OS functions.

1.3 Networks & Internet

• Network hardware: router, switch, hub, modem.
• IP address (IPv4) vs. MAC address – purpose of each.
• Packet switching & the OSI model (focus on layers 1‑4).
• Web protocols: HTTP, HTTPS – why encryption matters.
• URLs, domain names, DNS.
• Cookies & security: privacy, phishing, malware.

1.4 Emerging Technologies (Paper 2)

• Digital currency & blockchain – basic idea of a distributed ledger.
• Robotics & AI – sensors, actuators, simple decision‑making.
• Internet of Things (IoT) – examples such as smart home devices.
• Automation & cloud computing – advantages and potential drawbacks.

2. Algorithm Development – From Idea to Tested Program

2.1 The Development Cycle (AO1 & AO2)

1. Analyse the problem – list inputs, required outputs, constraints.
2. Design the algorithm – flowchart and/or pseudocode.
3. Implement – write the program (pseudo‑code for the exam).
4. Test & verify – validation + verification (see sections 3 & 4).
5. Document – comments, error messages, test data.

2.2 Flow‑chart Symbols (Paper 2)

Symbol	Name	Purpose
▭	Process	Assignment, arithmetic, input/output.
◇	Decision	True/false test (IF).
▶︎	Start/End	Oval – marks the program’s boundaries.
⇐▶︎	Connector	Joins separated parts of a large diagram.
⎕	Input/Output	Parallelogram – read or display data.

2.3 Pseudocode Conventions (AO1)

• All keywords in UPPERCASE (IF, THEN, ELSE, END IF, FOR, WHILE, REPEAT, UNTIL, READ, WRITE).
• Indentation shows block structure – one tab or four spaces per level.
• Identifiers start with a letter, may contain letters, digits or underscores.
• Comments begin with // or are enclosed in /* … */.
• Use meaningful variable names (e.g., mark, total, studentName).

2.4 Core Programming Constructs (AO2)

Selection

IF condition1 THEN
    …                // statements for condition1
ELSE IF condition2 THEN
    …                // statements for condition2
ELSE
    …                // default case
END IF

Iteration

• FOR – known number of repetitions.
  FOR i ← 1 TO n DO … END FOR
• WHILE – repeat while a condition is true.
  WHILE condition DO … END WHILE
• REPEAT … UNTIL – execute at least once.
  REPEAT … UNTIL condition

Arrays (1‑D & 2‑D)

// 1‑D array of 10 integers
DECLARE scores[10] AS INTEGER

// 2‑D array – 3 rows, 4 columns
DECLARE board[3][4] AS INTEGER

• Index starts at 0 (or 1, as specified by the exam).
• Nested loops are typical for traversing 2‑D arrays.

File Handling (Paper 2)

OPEN "results.txt" FOR WRITE AS f
WRITE f, "Alice", 85
CLOSE f

• Common commands: OPEN, CLOSE, READ, WRITE, APPEND.
• Always close a file to flush buffers.

Database Fundamentals & Simple SQL

• Table = collection of records (rows) with fields (columns).
• Primary key uniquely identifies a record.

SELECT name, mark
FROM students
WHERE mark >= 70
ORDER BY mark DESC;

Typical AO2 tasks: write a SELECT statement, identify the primary key, or describe the purpose of a WHERE clause.

Boolean Logic & Truth Tables (Paper 1)

A	B	A AND B	A OR B	NOT A
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

Gate symbols (AND, OR, NOT) are often required for circuit‑drawing questions.

Standard Algorithms (AO2)

• Totalling – sum of a list of numbers.
• Counting – number of items that satisfy a condition.
• Minimum / Maximum / Average.
• Linear search – find the position of a value in a 1‑D array.
• Bubble sort (simple version) – repeatedly swap adjacent out‑of‑order elements.

2.5 Mapping to Assessment Objectives

Section	AO1 (knowledge)	AO2 (application)	AO3 (evaluation)
Data representation	✓
Hardware & software	✓
Networks & internet	✓
Emerging tech	✓
Flow‑chart symbols	✓	✓
Pseudocode conventions	✓	✓
Selection & iteration	✓	✓
Arrays & nested loops	✓	✓
File handling	✓	✓
Database & SQL	✓	✓
Boolean logic & truth tables	✓	✓
Standard algorithms	✓	✓
Validation checks	✓	✓	✓
Verification techniques	✓	✓	✓

3. Validation – Checking the Input (AO2 + AO3)

3.1 Why Validation?

Before the main algorithm runs, the program must be sure that the data it receives satisfies the constraints set by the problem. Without validation the program may:

• Crash (division by zero, array‑index out of bounds).
• Produce mathematically incorrect results (overflow, underflow).
• Accept malicious data (e.g., injection attacks – relevant for Paper 2).

3.2 Types of Validation (Syllabus 7‑8)

Check	Description	Typical Exam Example
Type	Is the input an integer, real, character string, etc.?	Mark must be an INTEGER.
Range	Does the value lie between a lower and upper bound?	0 ≤ mark ≤ 100.
Format	Does the input follow a pattern (date, time, ISBN, email)?	DD/MM/YYYY.
Presence	Is a required field left empty?	Student name cannot be blank.
Check‑digit	Arithmetic rule that validates a code (ISBN, bar‑code, credit‑card).	ISBN‑10 check‑digit formula.

3.3 Validation Checklist (to write before coding)

1. List every input variable.
2. State its required type, range, format and any check‑digit rule.
3. Decide the error handling strategy:
   • Display a clear message (e.g., “Invalid mark – must be 0‑100”).
   • Terminate the algorithm or request a new input.

3.4 Example – ISBN‑10 Validation (Pseudo‑code)

READ isbn               // expects 10 characters
IF LENGTH(isbn) ≠ 10 THEN
    WRITE "ISBN must be 10 characters"
    STOP
END IF

sum ← 0
FOR i ← 1 TO 9 DO
    digit ← NUMERIC_VALUE(isbn[i])      // 0‑9
    sum ← sum + i * digit
END FOR
check ← (11 - (sum MOD 11)) MOD 11
IF check = 10 THEN
    expected ← 'X'
ELSE
    expected ← CHAR(check + 48)          // convert to character
END IF

IF isbn[10] = expected THEN
    WRITE "ISBN is valid"
ELSE
    WRITE "ISBN is invalid"
END IF

4. Verification – Checking the Algorithm’s Logic (AO2 + AO3)

4.1 What Verification Achieves

Verification confirms that, **given only valid inputs**, the algorithm always produces the correct output. It does not test the handling of bad data – that is the role of validation.

4.2 Verification Techniques

• Step‑by‑step tracing – use a trace table (dry‑run) for a chosen test case.
• Test‑data selection – at least one case from each category: Normal, Abnormal, Boundary, Extreme.
• Visual checks – compare algorithm’s output with a hand‑calculated result or a diagram.
• Double‑entry checks – run the same data twice (or with a partner) and compare results.
• Mathematical proof or induction – useful for sorting, summation, or recurrence algorithms.

4.3 Test‑Data Categories (Syllabus 7‑8)

Category	Purpose	Typical Example (Mark 0‑100)
Normal	Typical value inside the range.	73
Abnormal	Correct type but outside the permitted range.	-5 or 120
Boundary	Exact limits of the range.	0 and 100
Extreme	Largest/smallest valid values that stress the algorithm (e.g., very large n for a loop).	n = 0, n = 1000 (if allowed)

4.4 Trace‑Table Example – Grading Algorithm

Step	mark	Condition Tested	grade
1	85	mark ≥ 80	A
2	73	mark ≥ 80 ? No → mark ≥ 70	B
3	66	… ≥ 60	C
4	52	… ≥ 50	D
5	38	None of the above	F

4.5 Common Pitfall – Off‑by‑One Error

total ← 0
FOR i ← 1 TO n‑1 DO      // ❌ should be TO n
    total ← total + i
END FOR

How to locate:

1. Create a trace table for a small n (e.g., 5).
2. Notice the loop stops at i = 4, giving total = 10 instead of 15.
3. Correct the bound to FOR i ← 1 TO n DO.

5. Full Example – From Validation to Verification

Problem Statement

Write a program that reads a student’s numeric mark (0‑100) and outputs the corresponding grade (A‑F). Include validation of the input and verify the algorithm with appropriate test data.

5.1 Validation (before any calculation)

// 1. Type check – assume READ returns an integer; if not, the exam will state “integer input”.
READ mark
IF mark < 0 OR mark > 100 THEN
    WRITE "Error: mark must be between 0 and 100"
    STOP
END IF

5.2 Main Algorithm (verification part)

IF mark ≥ 80 THEN
    grade ← 'A'
ELSE IF mark ≥ 70 THEN
    grade ← 'B'
ELSE IF mark ≥ 60 THEN
    grade ← 'C'
ELSE IF mark ≥ 50 THEN
    grade ← 'D'
ELSE
    grade ← 'F'
END IF
WRITE "Grade:", grade

5.3 Test Data (AO3)

• Normal: 73 → B
• Boundary: 80 → A, 50 → D, 0 → F
• Abnormal: -3 → error message, 105 → error message
• Extreme: 100 → A (largest valid mark)

5.4 Trace Table (for normal case 73)

Line	mark	Test	grade
1	73	mark ≥ 80 ? No
2	73	mark ≥ 70 ? Yes	B

6. Practical Exam Tips (AO1‑AO3)

• Plan first: write a brief validation checklist, then sketch a flowchart or outline pseudocode.
• Include // validation and // main algorithm comments – they earn marks for clarity.
• Choose at least four test cases covering all four categories; label them clearly in your answer.
• Produce a full trace table for one normal case – show variable values after each step.
• If you run out of time, add a simple “error message” validation; it is better than none.
• Remember the AO mapping: validation → AO2 & AO3, verification (trace tables) → AO3, flow‑charts & pseudocode → AO1 & AO2.

7. Suggested Diagram