Use different methods to design and construct a solution to a problem

Algorithm Design and Problem‑Solving (Cambridge IGCSE 0478)

Learning Objective

Use a range of recognised methods to design, construct, test and evaluate a solution to a problem, covering both the computer‑systems context and the programming‑logic context required by the syllabus.

---

1. The Problem‑Solving Process (AO1 – AO3)

1. Understand the problem – read the specification carefully; note any assumptions and the required output format.
2. Analyse the problem – list
   • Inputs (type, range, format)
   • Outputs
   • Constraints (e.g. maximum size of a list, memory limits)
   • Special cases and error conditions
3. Decompose the problem – break it into smaller, manageable sub‑tasks (e.g. totalling, counting, finding max/min, calculating average).
4. Design an algorithm – choose a representation (pseudocode, flowchart, decision table, structured English) and apply a standard method of solution.
5. Implement the algorithm – translate the design into a programming language (or a high‑level pseudo‑language for the exam).
6. Test and debug – use trace tables, boundary‑value testing, and validation/verification checks.
7. Evaluate (AO3) – consider correctness, efficiency, readability, maintainability and compliance with the specification.

---

2. Computer Systems Overview (Syllabus Topics 1‑6)

2.1 Number Systems (Topic 1.1‑1.2)

• Binary, octal, decimal and hexadecimal representations.
• Conversions between bases – include both positive and negative numbers.
• Two’s‑complement for signed integers (example: -13 → 11110011 in 8‑bit two’s‑complement).
• Overflow detection (e.g. adding 200 + 100 in an 8‑bit unsigned system gives 44 with overflow flag set).

2.2 Data Transmission (Topic 1.3)

• Packet structure: header, payload, trailer.
• Switching methods: circuit, packet, message.
• Error‑detection techniques:
  • Parity bit (even/odd)
  • Checksum (simple sum of bytes)
  • CRC (brief mention)
• Simple ARQ (Automatic Repeat Request) model for retransmission.

2.3 Hardware (Topic 2)

• CPU architecture – fetch‑decode‑execute cycle, registers, ALU.
• Core, cache (L1/L2), and main memory hierarchy.
• Embedded systems and micro‑controllers.
• Input devices (keyboard, mouse, sensors) and output devices (monitor, printer, actuators).
• Storage hierarchy – primary (RAM), secondary (HDD/SSD), tertiary (magnetic tape, cloud).

2.4 Software (Topic 3)

• System software vs. application software.
• Operating system functions (resource management, file handling).
• Compiled vs. interpreted languages.
• Basic concepts of algorithms and flow‑control.

2.5 The Internet (Topic 4)

• URL structure, HTTP/HTTPS basics.
• DNS – translating domain names to IP addresses.
• Client‑server model and basic networking devices (router, switch).

2.6 Emerging & Automated Technologies (Topic 5‑6)

• Digital currency & blockchain – simple description of a block and hash.
• Cyber‑security basics – authentication, encryption, firewalls.
• Robotics and AI – sensors, actuators, simple decision‑making.
• Internet of Things (IoT) – connecting everyday objects.

---

3. Algorithms, Programming & Logic (Syllabus Topics 7‑10)

3.1 Standard Methods of Solution

Method	Purpose	Typical Pseudocode Pattern
Totalling / Counting	Accumulate a sum or a count while iterating.	SET total←0; REPEAT … SET total←total+value … END REPEAT
Maximum / Minimum (Linear Search)	Find the extreme value in a list.	SET max←‑∞; REPEAT … IF value>max THEN SET max←value END IF … END REPEAT
Average	Mean = total / count (use floating‑point if required).	SET avg←total / count
Sorting (Bubble Sort)	Arrange data in ascending/descending order.	FOR i←1 TO n‑1 REPEAT FOR j←1 TO n‑i IF a[j]>a[j+1] THEN SWAP a[j],a[j+1] END IF END REPEAT END FOR
Search (Linear / Binary)	Locate a specific value.	Linear: REPEAT … IF a[i]=key THEN FOUND←TRUE END IF … END REPEAT Binary: WHILE low≤high …

3.2 Logic‑Gate & Flowchart Symbols (Quick Reference)

3.3 Pseudocode Conventions – Style Guide (Cambridge‑approved)

Element	Convention
Keywords	Upper‑case (READ, OUTPUT, IF, THEN, ELSE, END IF, REPEAT, UNTIL, WHILE, END WHILE, FOR, END FOR)
Indentation	Two spaces per block level; no tabs.
Meta‑variables	Italicised or enclosed in <> (e.g. <score>) to show placeholders.
Line numbers	Optional but useful for discussion; format “1.”, “2.” …
Comments	Start with // or REM. Keep them brief and on their own line.
Assignments	Use the arrow symbol ← (or = if arrow unavailable).
Loop controls	REPEAT … UNTIL condition or FOR i FROM 1 TO n … END FOR.

3.4 Design Methods

3.4.1 Pseudocode (example – score‑analysis problem)

1.  SET count   ← 0
2.  SET total   ← 0
3.  SET highest ← -1
4.  SET lowest  ← 101
5.  REPEAT
6.      READ <score>
7.      IF <score> < 0 THEN
8.          EXIT REPEAT
9.      END IF
10.     IF <score> > 100 OR <score> < 0 THEN
11.         OUTPUT "Invalid – enter 0‑100"
12.         CONTINUE REPEAT
13.     END IF
14.     SET count   ← count + 1
15.     SET total   ← total + <score>
16.     IF <score> > highest THEN SET highest ← <score> END IF
17.     IF <score> < lowest THEN SET lowest ← <score> END IF
18. END REPEAT
19. IF count = 0 THEN
20.     OUTPUT "No scores entered."
21. ELSE
22.     SET average ← total / count
23.     OUTPUT "Count:", count,
24.            "Highest:", highest,
25.            "Lowest:", lowest,
26.            "Average:", ROUND(average,2)
27. END IF

3.4.2 Flowchart (example)

3.4.3 Decision Table (example)

Condition	Score < 0	0 ≤ Score ≤ 100	Score > 100 or < 0 (invalid)
Action	Terminate loop	Update count, total, highest, lowest	Display error, repeat input

3.4.4 Structured English (example)

BEGIN
    SET count = 0, total = 0, highest = -1, lowest = 101
    REPEAT
        READ score
        IF score < 0 THEN EXIT REPEAT END IF
        IF score > 100 OR score < 0 THEN
            OUTPUT "Invalid score – must be 0‑100"
            CONTINUE REPEAT
        END IF
        SET count = count + 1
        SET total = total + score
        IF score > highest THEN SET highest = score END IF
        IF score < lowest THEN SET lowest = score END IF
    END REPEAT
    IF count > 0 THEN
        SET average = total / count
        OUTPUT count, highest, lowest, average
    ELSE
        OUTPUT "No scores entered."
    END IF
END

---

4. Validation vs. Verification

Aspect	Validation (Input Checking)	Verification (Output Checking)
Purpose	Ensure data entered meets type, range, length or format requirements before it is processed.	Confirm that the algorithm produces the expected results for given inputs.
Typical Checks	Range (0 ≤ score ≤ 100), type (numeric), termination condition (negative number).	Trace tables, boundary‑value testing, comparison with hand‑calculated results.
When Performed	During input stage, before any calculation.	After the algorithm has run – during testing/debugging.

---

5. Example Problem – Score Analysis

5.1 Specification

Write a program that reads a list of integer scores (0‑100) entered by the user, terminated by a negative number. The program must output:

• Number of scores entered.
• Highest and lowest scores.
• Average score rounded to two decimal places.
• (Extension) Number of scores above the calculated average.

5.2 Decomposition

1. Read a score.
2. Validate the score (0‑100).
3. Update count, total, highest, lowest.
4. Repeat until a negative score is entered.
5. Calculate average.
6. (Extension) Count scores > average.
7. Display results.

5.3 Pseudocode (with line numbers – Cambridge style)

1.  SET count   ← 0
2.  SET total   ← 0
3.  SET highest ← -1
4.  SET lowest  ← 101
5.  REPEAT
6.      READ <score>
7.      IF <score> < 0 THEN
8.          EXIT REPEAT
9.      END IF
10.     IF <score> > 100 OR <score> < 0 THEN
11.         OUTPUT "Invalid – enter 0‑100"
12.         CONTINUE REPEAT
13.     END IF
14.     SET count   ← count + 1
15.     SET total   ← total + <score>
16.     IF <score> > highest THEN SET highest ← <score> END IF
17.     IF <score> < lowest THEN SET lowest ← <score> END IF
18. END REPEAT
19. IF count = 0 THEN
20.     OUTPUT "No scores entered."
21. ELSE
22.     SET average ← total / count
23.     /* Extension – count scores above average */
24.     SET aboveAvg ← 0
25.     REPEAT FOR i FROM 1 TO count
26.         IF score[i] > average THEN SET aboveAvg ← aboveAvg + 1 END IF
27.     END REPEAT
28.     OUTPUT "Count:", count,
29.            "Highest:", highest,
30.            "Lowest:", lowest,
31.            "Average:", ROUND(average,2),
32.            "Above average:", aboveAvg
33. END IF

5.4 Trace Table (dry‑run)

Step	score (input)	count	total	highest	lowest
Start	–	0	0	-1	101
1	85	1	85	85	85
2	70	2	155	85	70
3	90	3	245	90	70
4	-1	3	245	90	70

5.5 Decision Table (expanded)

Condition	Score < 0	0 ≤ Score ≤ 100	Score > 100 or < 0 (invalid)
Action	Terminate loop	Update count, total, highest, lowest	Display error, repeat input

5.6 Evaluation Checklist (AO3)

Criterion	What to Check
Correctness	All test cases (normal, boundary, error) produce the expected output; trace tables confirm logic.
Efficiency	Time = O(n) – single pass for totals and extremes; Space = O(1) – only a few scalar variables (or O(n) if storing the list for the extension).
Readability	Consistent indentation, meaningful variable names, comments for validation steps.
Maintainability	Algorithm is modular – each sub‑task could be placed in a separate function or procedure.
Compliance with Specification	All required outputs are produced; the optional “above‑average” count is clearly separated.

Model AO3 Response (excerpt)

“The algorithm is correct because it has been tested with normal data (85, 70, 90), boundary data (0, 100) and error data (‑5, 150). In each case the trace table matches the expected results, confirming the logic. It runs in linear time O(n) and uses only four integer variables, so it is efficient in both time and space. The use of uppercase keywords, two‑space indentation and clear variable names makes the pseudocode easy to read. All parts of the specification are met: the programme reports the count, highest, lowest and average, and the optional part correctly counts scores above the average. Therefore the solution fully satisfies the problem requirements.”

---

6. Sample Test Cases

1. Input: 85, 70, 90, -1
   Expected Output: Count = 3, Highest = 90, Lowest = 70, Average = 81.67
2. Input: 0, 100, 50, -1
   Expected Output: Count = 3, Highest = 100, Lowest = 0, Average = 50.00
3. Input: -1
   Expected Output: “No scores entered.”
4. Input (invalid): 105, 80, -1
   Expected Behaviour: Display error for 105, then process 80 → Count = 1, Highest = 80, Lowest = 80, Average = 80.00

---

7. Extension Activity

Modify the algorithm to count how many scores are above the calculated average and display this number. Two approaches are possible:

• Two‑pass method – store each valid score in an array, calculate the average, then loop through the array a second time to count scores > average.
• Single‑pass method – maintain a running total and count, then after the first pass calculate the average and re‑iterate through the stored array (requires storage) or, if the language permits, use a dynamic list.

Both approaches should be evaluated for time and space efficiency using the checklist in Section 6.

---

8. Key Points to Remember

• Start every problem with a clear analysis – list inputs, outputs, constraints and special cases.
• Choose the appropriate standard method of solution (totalling, counting, max/min, average, sorting, searching).
• Use Cambridge‑approved pseudocode conventions; they aid readability and mark‑scheme matching.
• Separate validation (checking input) from verification (checking output). Use a side‑by‑side table to remind yourself of the difference.
• Test thoroughly:
  • Normal data (e.g., 85, 70, 90)
  • Boundary values (0, 100)
  • Error data (‑5, 150, non‑numeric)
• After testing, evaluate the solution on correctness, efficiency, readability, maintainability and compliance with the specification (AO3).
• Iterate – refine the algorithm after each round of testing and evaluation.