Understand standard methods of solution

Cambridge IGCSE Computer Science (0478) – Complete Syllabus Notes

---

1. Assessment Overview

The IGCSE Computer Science (0478) specification is divided into two balanced halves:

• Computer‑systems – Topics 1‑6 (Data representation, data transmission, hardware, software, the Internet, automated & emerging technologies).
• Algorithms, programming & logic – Topics 7‑10 (Problem solving, standard solution methods, algorithm representation, testing & evaluation).

Both halves are tested in Paper 1 (the non‑programming paper) and Paper 2 (the programming paper). The notes below cover **all** required topics and provide the tools needed to answer any exam question.

---

2. The Problem‑Solving Process (Program‑development Life‑cycle)

1. Understand the problem – read the specification, note constraints, special cases and required output.
2. Analyse – list inputs, outputs, data types, validation rules and any calculations needed.
3. Design – choose a standard method, decompose the problem, and produce a high‑level description (flowchart or pseudocode).
4. Implement – translate the design into a programming language (or detailed pseudocode).
5. Test & Debug – create test data (normal, boundary, invalid, special), run the program, use trace tables and locate/correct errors.
6. Evaluate – consider efficiency (time/space), readability, maintainability and whether the solution meets the specification.

---

3. Computer‑Systems (Topics 1‑6)

3.1 Data Representation

• Number systems – binary (base 2), denary/decimal (base 10), hexadecimal (base 16).
• Conversions – use repeated division for binary⇔decimal, group 4 bits for binary⇔hex.
• Two’s‑complement – represent signed integers; invert bits and add 1 to get the negative.
• Overflow – occurs when the result exceeds the range that can be stored in the given number of bits.
• Shift operations – logical left/right shift (multiply/divide by 2), arithmetic right shift preserves sign.

Decimal	Binary (8‑bit)	Hexadecimal
45	0010 1101	0x2D
-13 (two’s‑complement)	1111 0011	0xF3
255	1111 1111	0xFF

Worked conversion example – Convert 0x3A to binary and decimal:

0x3A = 3·16 + A
      = 3·16 + 10 = 58₁₀
Binary: 0011 1010₂

---

3.2 Data Transmission & Error Detection

• Packet structure – header (address, control), payload (data), trailer (checksum).
• Transmission media – USB (serial, high‑speed), serial vs parallel cables, wireless (Wi‑Fi, Bluetooth).
• Communication modes – simplex, half‑duplex, full‑duplex.
• Error‑detection techniques
  • Parity bit (even/odd)
  • Checksum (sum of bytes modulo 256)
  • CRC (Cyclic Redundancy Check – not required for the exam but useful to know)
• ARQ (Automatic Repeat reQuest) – simple protocol that retransmits a packet when an error is detected.
• Encryption
  • Symmetric (same key for encrypt & decrypt – e.g., AES)
  • Asymmetric (public‑key & private‑key – e.g., RSA)

Example – Even parity check

Data byte: 1010 0110
Number of 1s = 4 (even) → parity bit = 0
Transmitted byte = 1010 0110 0

---

3.3 Hardware

• CPU operation – Fetch → Decode → Execute cycle (stored‑program concept).
• Registers – Program Counter (PC), Instruction Register (IR), Accumulator (ACC), general‑purpose registers.
• ALU (Arithmetic‑Logic Unit) – performs arithmetic and logical operations.
• Control Unit – generates control signals to coordinate the CPU.
• Core & Cache – multi‑core CPUs run parallel threads; cache (L1, L2) stores frequently used data for speed.
• Buses – data bus, address bus, control bus.
• Embedded systems – computers built into devices (e.g., microwaves, cars) with dedicated functions.

Labelled diagram (textual)

[Input Devices] → [Bus] → [CPU]
                 ↘︎          ↙︎
               [Memory]   [Output Devices]

---

3.4 Software

• System software – Operating System (OS) manages resources, provides file system, multitasking, security.
• Application software – programs that perform specific tasks for the user (e.g., word processor, web browser).
• OS functions – process scheduling, memory management, I/O handling, device drivers, interrupts.
• Interrupts – hardware or software signals that temporarily halt the CPU to service an event.
• Programming language levels
  • Low‑level (machine code, assembly)
  • High‑level (Python, Java, Pascal)
• Compilers vs Interpreters

  Aspect	Compiler	Interpreter
  Translation	Whole program → machine code	Line‑by‑line execution
  Speed of execution	Fast (after compilation)	Slower (interpreted each time)
  Error detection	All syntax errors found before run	Stops at first runtime error

• Integrated Development Environments (IDEs) – combine editor, compiler/interpreter, debugger, and often a visual designer.

---

3.5 The Internet & Emerging Technologies

• Internet vs World Wide Web – Internet is the global network; the Web is a service that uses HTTP/HTTPS.
• URL structure – protocol://domain[:port]/path?query#fragment
• HTTP/HTTPS – request/response protocol; HTTPS adds TLS encryption.
• Web browsers – interpret HTML, CSS, JavaScript to display pages.
• DNS (Domain Name System) – translates domain names to IP addresses.
• Cookies – small data stored on the client to maintain state (e.g., login sessions).
• Digital currency & blockchain – decentralized ledger; each block contains a hash of the previous block.

Web request flow (simplified)

User clicks link → Browser sends HTTP GET → DNS resolves domain → TCP handshake → Server processes request → Server sends HTML → Browser renders page

---

3.6 Automated & Emerging Technologies

• Sensors – convert physical quantities (temperature, light, pressure) into electrical signals.
• Actuators – convert electrical signals into motion (motors, solenoids).
• Robotics – integration of sensors, actuators, control software to perform tasks.
• Artificial Intelligence (AI) – machines that mimic human reasoning (search, knowledge representation).
• Expert systems – AI applications that use a knowledge base and inference engine to solve domain‑specific problems.
• Machine Learning (ML) – algorithms that improve performance from data (e.g., decision trees, neural networks).

---

4. Standard Methods of Solution (Topics 7‑10)

4.1 Overview Table

Method	Typical Use‑case	Key Idea	Complexity (Big‑O)
Linear Search	Find a value in an unsorted list	Check each element sequentially	O(n)
Bubble Sort	Sort a small‑to‑moderate list	Repeatedly swap adjacent out‑of‑order items	O(n²)
Totalling (Summation)	Add all numbers in a list or range	Accumulator pattern	O(n)
Counting	Count items that satisfy a condition	Increment a counter when condition true	O(n)
Maximum / Minimum	Find largest or smallest value	Track current best value while scanning	O(n)
Average (Mean)	Calculate arithmetic mean	Sum then divide by count	O(n)

4.2 Detailed Method Descriptions

Linear Search

When to use: List is unsorted and only one occurrence is needed.

INPUT target, list[ ]
FOR i FROM 0 TO LENGTH(list)-1
    IF list[i] = target THEN
        OUTPUT "Found at position", i
        STOP
    END IF
END FOR
OUTPUT "Not found"

Flow‑chart description – Start → Input → Loop (i = 0 …) → Decision (list[i] = target?) → Yes → Output position → Stop; No → Continue loop → After loop → Output “Not found” → Stop.

Bubble Sort

When to use: Small data sets where simplicity outweighs speed.

INPUT list[ ]
SET swapped = true
WHILE swapped
    SET swapped = false
    FOR i FROM 0 TO LENGTH(list)-2
        IF list[i] > list[i+1] THEN
            SWAP list[i], list[i+1]
            SET swapped = true
        END IF
    END FOR
END WHILE
OUTPUT list

Totalling (Summation)

INPUT numbers[ ]
SET total = 0
FOR i FROM 0 TO LENGTH(numbers)-1
    SET total = total + numbers[i]
END FOR
OUTPUT total

Counting

INPUT data[ ]
SET count = 0
FOR i FROM 0 TO LENGTH(data)-1
    IF data[i] MOD 2 = 0 THEN
        SET count = count + 1
    END IF
END FOR
OUTPUT count

Maximum / Minimum

INPUT values[ ]
SET max = values[0]          // for minimum use SET min = values[0]
FOR i FROM 1 TO LENGTH(values)-1
    IF values[i] > max THEN
        SET max = values[i]
    END IF
END FOR
OUTPUT max

Average (Mean)

INPUT scores[ ]
SET total = 0
FOR i FROM 0 TO LENGTH(scores)-1
    SET total = total + scores[i]
END FOR
SET average = total / LENGTH(scores)
OUTPUT average

4.3 Other General Methods (Useful for Higher‑level Questions)

• Brute‑Force (Exhaustive Search)
• Divide and Conquer (e.g., binary search, merge sort)
• Greedy Algorithms (e.g., coin‑change)
• Dynamic Programming (e.g., Fibonacci, knapsack)
• Backtracking (e.g., Sudoku, N‑Queens)
• Recursive Design
• Iterative (Loop‑Based) Design

---

5. Representing Algorithms

5.1 Flowchart Symbols (Cambridge‑approved)

Symbol	Name	Purpose
Oval	Start / End	Marks the entry and exit points
Parallelogram	Input / Output	Read data or display results
Rectangle	Processing	Assignment, calculation, or function call
Diamond	Decision	Yes/No (True/False) test
Arrows	Flow of control	Shows the direction of execution

5.2 Pseudocode Conventions (used in the exam)

• All keywords in UPPERCASE (e.g., IF, FOR, END IF).
• Indentation indicates block structure.
• Use meaningful variable names (e.g., totalScore, maxMark).
• Array indexing starts at 0 unless the specification states otherwise.
• Comments begin with // or #.

---

6. Validation & Verification (Checking Input Data)

Every input should be validated before it is used in calculations.

Check	What to Test	Example
Range	Value lies between a minimum and maximum	Age 0 ≤ age ≤ 120
Length	String length is within allowed limits	Username 5–12 characters
Type	Correct data type (integer, real, string, Boolean)	Score must be an integer
Presence	Mandatory fields are not empty	Student ID cannot be blank
Format	Matches a pattern (email, date, postcode)	Postcode “AA9 9AA”
Check‑digit / checksum	Simple arithmetic test	Validate credit‑card number with Luhn algorithm

Validation example – Age input

INPUT age
IF age < 0 OR age > 120 THEN
    OUTPUT "Invalid age – must be 0‑120"
    STOP
END IF

---

7. Test Data Design & Trace Tables

7.1 Types of Test Data

• Normal (valid) data – typical values within the expected range.
• Boundary data – values at the minimum, maximum, just inside and just outside the limits.
• Invalid data – values that break a validation rule.
• Special cases – empty input, single‑element list, duplicate values, already sorted data, etc.

7.2 Example Trace Table – Linear Search for 7 in [3, 7, 2, 7]

Step	i	list[i]	Found?
1	0	3	No
2	1	7	Yes – stop

7.3 Using a Trace Table to Debug

1. Run the algorithm with a small, known test case.
2. After each statement, record the values of all relevant variables.
3. Compare the recorded values with the expected ones.
4. Locate the first step where the values diverge – this is where the error lies.
5. Correct the code, then repeat testing.

---

8. Error Identification & Common Pitfalls

• Syntax errors – misspelled keywords, missing END IF, wrong punctuation.
• Logic errors – wrong condition, off‑by‑one in loops, using the wrong variable in a calculation.
• Runtime errors – division by zero, array index out of bounds, infinite loops.
• Data‑type mismatches – adding a string to a number, comparing different types.
• Missing validation – program crashes or produces wrong output on illegal input.

Typical debugging steps

1. Read any error message carefully.
2. Test with the smallest possible data set.
3. Insert print statements or use a trace table to watch variable values.
4. Check loop start/end values and conditional expressions.
5. Fix the identified issue, then re‑run all test data.

---

9. Choosing the Appropriate Method – Decision Checklist

1. Is the data set small enough for a simple brute‑force or linear approach?
2. Do I need the data sorted? – consider Bubble Sort (small) or a more efficient sort for larger sets.
3. Am I only counting, totalling, or finding a max/min/average? – use the dedicated single‑loop methods.
4. Can the problem be divided into independent sub‑problems? – think Divide and Conquer.
5. Does a locally optimal (greedy) choice guarantee a global optimum? – use a greedy algorithm.
6. Do sub‑problems overlap? – Dynamic Programming may be required.
7. Do I need to explore many possibilities with constraints? – Backtracking.
8. Is the solution naturally expressed as “solve a smaller instance of the same problem”? – Recursion.
9. Otherwise, a straightforward iterative loop is usually best.

---

10. Summary

• Master the six‑step problem‑solving cycle; apply it to both computer‑systems and algorithm questions.
• For **computer‑systems**: understand data representation, transmission, hardware, software, the Internet and emerging technologies – these are the focus of Paper 1.
• For **algorithms**: recognise the exact standard method required (linear search, bubble sort, totalling, counting, max/min, average) and implement it correctly.
• Validate every input, design comprehensive test data, and use trace tables to verify logic.
• Represent solutions clearly with either a flowchart (standard symbols) or well‑structured pseudocode.
• Evaluate efficiency (time/space), readability and maintainability before finalising your answer.