Understand and apply standard search and sort algorithms (e.g. linear search, bubble sort)

1. Computer Systems – Core Concepts (Syllabus 1‑6)

1.1 Data Representation

• Number systems
  • Binary, hexadecimal and decimal – conversion is essential for low‑level programming.
  • Typical 8‑bit conversion table:

  Binary	Hex	Decimal
  0000 0000	00	0
  0000 0001	01	1
  0000 0010	02	2
  0000 0011	03	3
  1111 1111	FF	255

  Example: 10110110₂ = B6₁₆ = 182₁₀

• Two’s‑complement for signed integers
  • To obtain –x: invert all bits of x and add 1.
  • Example (8‑bit): –45 → 45₁₀ = 0010 1101₂ → invert = 1101 0010 → add 1 = 1101 0011₂.
• Character encoding
  • ASCII – 7‑bit code (e.g. ‘A’ = 65₁₀ = 41₁₆).
  • Unicode – extends ASCII to represent world‑wide scripts (UTF‑8, UTF‑16).
• Image representation
  • Pixels × colour depth (bits per pixel).
  • Example: 640 × 480 colour image at 24‑bit depth 640 × 480 × 24 bits = 7 372 800 bits ≈ 0.88 MB.
  • Lossless compression (e.g., PNG, ZIP) preserves every pixel; lossy compression (e.g., JPEG, MP3) discards information that is less perceptible.
• Sound representation
  • Sampling rate × bit depth × number of channels.
  • Example: CD‑quality audio = 44 100 samples · 16 bits · 2 channels ≈ 1.41 Mbps.
  • Lossless audio (FLAC) vs. lossy audio (MP3, AAC).
• Data compression

  Type	Method	Typical Use
  Lossless	ZIP, PNG, FLAC	Text files, executables, archival storage
  Lossy	JPEG, MP3, MPEG‑4	Photos, music, video streaming

1.2 Data Transmission

• Packet structure

  | Header | Payload (data) | Trailer |
  |--------|----------------|---------|
  | source address, destination address, control bits | user data | error‑check bits (e.g., CRC) |
          

• Error‑detection and correction
  • Parity bit – simple even/odd check.
  • Checksum – sum of all bytes, stored in trailer.
  • CRC (Cyclic Redundancy Check) – polynomial division; common 16‑bit CRC‑CCITT.
  • ARQ (Automatic Repeat reQuest) – sender retransmits if receiver reports an error (Stop‑and‑Wait, Go‑Back‑N, Selective Repeat).
• Common transmission media
  • Copper: Ethernet (Cat 5e, Cat 6), coaxial cable.
  • Fibre‑optic: high‑speed, low‑loss, immune to EMI.
  • Wireless: Wi‑Fi (802.11 a/b/g/n/ac/ax), Bluetooth, infrared.
• Simple encryption example – Caesar cipher

  Plaintext:  ATTACK
  Shift +3 → Ciphertext: DWWDFN
          

  (Each letter is moved three positions forward in the alphabet; wraps from Z to A.)
• Switching techniques
  • Circuit switching – dedicated path (telephone networks).
  • Packet switching – data broken into packets, routed independently (Internet).

1.3 Storage Units & Memory Hierarchy

Memory hierarchy (fast → slow)

• Registers – inside the CPU, fastest access.
• Cache (L1, L2, L3) – small, high‑speed SRAM.
• Main RAM – volatile DRAM.
• Secondary storage – HDD, SSD.
• Optical media – CD/DVD/Blu‑ray.
• Cloud / network storage – accessed via Internet.

2. Hardware & Software (Syllabus 3‑5)

2.1 Hardware Overview

• CPU (Central Processing Unit)
  • Components: Control Unit, Arithmetic‑Logic Unit (ALU), registers.
  • FDE cycle – Fetch, Decode, Execute of each instruction.
  • Clock speed (MHz/GHz) determines cycles per second.
  • Multi‑core processors – parallel execution of independent threads.
  • Cache hierarchy (L1‑L3) reduces average memory access time.
• Instruction set – set of binary commands a CPU can execute (e.g., RISC vs. CISC).
• Micro‑processor vs. micro‑controller
  • Micro‑processor: CPU only, requires external RAM/ROM (e.g., desktop PC).
  • Micro‑controller: CPU + RAM + ROM + I/O peripherals on a single chip (e.g., Arduino, automotive ECUs).
• Embedded systems – specialised computers built into appliances, cars, IoT devices.
• Input/Output devices
  • Input: keyboard, mouse, scanner, microphone, touch screen.
  • Output: monitor, printer, speaker, LED display.
  • Interfaces: USB, HDMI, Bluetooth, Wi‑Fi, GPIO.
• Network hardware
  • Router, switch, modem, access point.
  • Ethernet cables (Cat 5e, Cat 6) – up to 10 Gb/s.
  • Wireless standards – 802.11a/b/g/n/ac/ax.

2.2 Software Layers

2.3 Interrupts & Handling Flow

• When an interrupt request (IRQ) arrives, the CPU:
  1. Finishes the current instruction.
  2. Saves the current program counter and registers (state) on the stack.
  3. Jumps to the Interrupt Service Routine (ISR) address.
  4. Executes the ISR – handles the event (e.g., keyboard press, timer tick).
  5. Restores the saved state.
  6. Resumes the interrupted program.

2.4 Programming Languages & Tools

• Compilers vs. Interpreters

  Feature	Compiler	Interpreter
  Translation	Whole source → machine code before execution	Source executed line‑by‑line at run‑time
  Speed	Fast execution (code already compiled)	Slower execution (translation on the fly)
  Error detection	All syntax errors caught before run‑time	Errors detected as each line is executed
  Examples	C, C++, Java (javac)	Python, BASIC, JavaScript (node)

• Integrated Development Environments (IDEs)
  • Combine editor, compiler/interpreter, debugger, and project management.
  • Common features: syntax highlighting, code completion, version‑control integration, visual debugging.
  • Examples: Eclipse, Visual Studio, PyCharm, BlueJ.

3. The Internet, Cyber‑Security & Emerging Technologies (Syllabus 5‑6)

3.1 Internet & Web Fundamentals

• URL structure – protocol://host[:port]/path?query#fragment
  Example: https://www.example.com:443/articles?id=7#section2
• Request‑response cycle

  

• HTTP vs. HTTPS – HTTPS adds TLS encryption for confidentiality, integrity and authentication.
• Web browsers – render HTML/CSS, execute JavaScript, manage cookies and cache.
• DNS (Domain Name System) – hierarchical, distributed database that maps domain names to IP addresses.
• Common protocols
  • TCP/IP – reliable, connection‑oriented.
  • UDP – connection‑less, low latency (e.g., streaming, gaming).
  • FTP – file transfer.
  • SMTP – sending e‑mail.
  • POP3 / IMAP – retrieving e‑mail.

3.2 Cyber‑Security Checklist

3.3 Emerging Technologies

• Digital currency & blockchain
  • Decentralised ledger where each block contains a hash of the previous block.
  • Simple diagram:

  

• Robotics & Artificial Intelligence
  • Robot architecture: sensor → controller → actuator.
  • Expert system – rule‑based decision making (IF‑THEN rules).
  • Machine learning – algorithms that improve from data (e.g., classification, regression).
• Internet of Things (IoT)
  • Networked sensors/actuators, often low‑power micro‑controllers.
  • Typical stack: sensors → micro‑controller (e.g., ESP32) → Wi‑Fi → cloud platform.

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

4.1 Pseudocode Conventions (Cambridge style)

• Keywords in UPPERCASE: IF … THEN … END IF, FOR … TO … NEXT, WHILE … DO … END WHILE.
• Indentation indicates block structure.
• Variable names should be meaningful (e.g., totalScore).
• Comments start with // (single line) or /* … */ (block).

4.2 Standard Search Algorithms

4.2.1 Linear (Sequential) Search

Exam‑style description: examines each element in order until the target is found or the list ends.

FOR i FROM 0 TO n‑1
    IF list[i] = target THEN
        RETURN i          // index of target
    END IF
NEXT i
RETURN -1                 // not found

Complexity

• Worst‑case time: O(n)
• Best‑case time: O(1) (target is first element)
• Space: O(1)

4.2.2 Binary Search (requires a sorted list)

low  ← 0
high ← n‑1
WHILE low ≤ high
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        RETURN mid
    ELSE IF list[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid – 1
    END IF
END WHILE
RETURN -1

Complexity

• Time: O(log n)
• Space: O(1) (iterative version)

4.3 Standard Sort Algorithms

4.3.1 Bubble Sort

REPEAT
    swapped ← FALSE
    FOR i FROM 0 TO n‑2
        IF list[i] > list[i+1] THEN
            SWAP list[i] AND list[i+1]
            swapped ← TRUE
        END IF
    NEXT i
UNTIL swapped = FALSE

Complexity

• Best‑case (already sorted): O(n)
• Average & worst‑case: O(n²)
• Space: O(1) (in‑place)

4.3.2 Insertion Sort

FOR i FROM 1 TO n‑1
    key ← list[i]
    j   ← i‑1
    WHILE j ≥ 0 AND list[j] > key
        list[j+1] ← list[j]
        j ← j‑1
    END WHILE
    list[j+1] ← key
NEXT i

Complexity

• Best‑case (already sorted): O(n)
• Average & worst‑case: O(n²)
• Space: O(1)

4.3.3 Selection Sort

FOR i FROM 0 TO n‑2
    minIndex ← i
    FOR j FROM i+1 TO n‑1
        IF list[j] < list[minIndex] THEN
            minIndex ← j
        END IF
    NEXT j
    SWAP list[i] AND list[minIndex]
NEXT i

Complexity

• Time (all cases): O(n²)
• Space: O(1)
• Fewer swaps than bubble sort – useful when write‑operations are expensive.

4.3.4 When to Use Simple O(n²) Sorts

• Educational contexts – illustrate algorithm design, analysis and debugging.
• Very small data sets (≤ 20 items) where overhead of more complex algorithms outweighs benefits.
• Situations where stability is not required and memory is limited.

4.4 Common Programming Tasks (Syllabus 7‑10)

total ← 0
FOR i FROM 0 TO n‑1
    total ← total + list[i]
NEXT i

count ← 0
FOR i FROM 0 TO n‑1
    IF condition(list[i]) THEN
        count ← count + 1
    END IF
NEXT i

max ← list[0]
FOR i FROM 1 TO n‑1
    IF list[i] > max THEN
        max ← list[i]
    END IF
NEXT i

total ← 0
FOR i FROM 0 TO n‑1
    total ← total + list[i]
NEXT i
average ← total / n

FOR i FROM 0 TO n‑1
    IF list[i] = oldValue THEN
        list[i] ← newValue
    END IF
NEXT i

4.5 Algorithm Analysis – Big‑O Notation (Exam focus)

• Time complexity – how the number of operations grows with input size n.
  • Constant: O(1)
  • Logarithmic: O(log n)
  • Linear: O(n)
  • Linearithmic: O(n log n)
  • Quadratic: O(n²)
  • Exponential: O(2ⁿ)
• Space complexity – additional memory required beyond the input data.
• When answering exam questions, always state the best, average and worst‑case where relevant, and justify with a brief explanation (e.g., “each element is compared once, giving O(n)”).