Use suitable identifier names for the representation of data used by a problem and represent these using an identifier table

Cambridge A‑Level Computer Science (9618) – Syllabus Notes

1. Algorithms: Using Suitable Identifier Names and Identifier Tables

1.1 Why identifiers matter

• Give meaning to data items (variables, constants, arrays, records, functions).
• Make pseudocode readable without excessive comments.
• Reduce translation errors when converting to a programming language.

1.2 Guidelines for choosing identifier names

1. Be descriptive – e.g. totalScore rather than ts.
2. Use a consistent case style – CamelCase (totalScore) or snakecase (totalscore).
3. Limit abbreviations – only widely‑known ones such as avg, cnt.
4. Reflect data type when helpful – num for integers, is for booleans, arr for arrays.
5. Keep it short but clear – avoid overly long names that clutter the algorithm.

1.3 The Identifier Table

An identifier table records every data item used by an algorithm together with its type, purpose and a sample value.

1.4 Worked example – Class average

Problem: “Given the marks of all students in a class, determine the average mark and how many students passed (mark ≥ 50).”

1. Identify inputs – an array marks[1…n].
2. Identify required outputs – averageMark and passedCount.
3. Derive intermediate data – totalMarks, numStudents, isPass.
4. Choose data types – integers for counts, real for the average, boolean for the flag.
5. Populate the identifier table (see above).

INPUT marks[1 … n]
SET totalMarks ← 0
SET passedCount ← 0
SET numStudents ← n
FOR i ← 1 TO n DO
SET totalMarks ← totalMarks + marks[i]
IF marks[i] ≥ 50 THEN
SET passedCount ← passedCount + 1
END IF
END FOR
SET averageMark ← totalMarks / numStudents
OUTPUT averageMark, passedCount

1.5 Practice exercise

Write an identifier table for the problem: “A library keeps a record of each book’s ISBN (13‑digit number), title, author, and whether it is currently on loan. Write an algorithm that counts how many books are on loan and lists the titles of books that are not on loan.”

After the table, draft a brief pseudocode outline using your identifiers.

2. Information Representation

2.1 Number systems

• Binary (base‑2), Octal (base‑8), Decimal (base‑10), Hexadecimal (base‑16).
• Conversions – repeated division (to a lower base) and repeated multiplication (to a higher base).

2.2 Binary arithmetic and two’s‑complement

• Addition and subtraction using two’s‑complement for negative numbers.
• Overflow detection – occurs when the carry‑out of the most‑significant bit is discarded.
• Example (8‑bit two’s‑complement):

  0101 0011   (+83)
  + 1010 1101   (‑83)
  -------------
  0000 0000   (Result 0, no overflow)
  

2.3 Binary‑coded decimal (BCD)

Each decimal digit is stored in a separate 4‑bit nibble.

Decimal  57  →  BCD 0101 0111
Addition in BCD requires a correction of +6 when a nibble exceeds 9.

2.4 Floating‑point representation (IEEE 754 single precision)

• 32 bits: 1 sign bit, 8 exponent bits (bias = 127), 23 mantissa bits.
• Value = (‑1)^sign × 1.mantissa × 2^{(exponent‑127)}
• Example: ‑3.75 → 1 01111111 11110000000000000000000

2.5 Character encoding

• ASCII – 7‑bit, 0‑127 characters (e.g. ‘A’ → 65 → 01000001₂).
• Unicode – supports world‑wide scripts; UTF‑8 uses 1‑4 bytes, UTF‑16 uses 2‑4 bytes.

2.6 Multimedia representation

Images

• Bitmap (raster) – stores colour of each pixel.

  • Colour depth (bits per pixel) determines the number of colours (e.g. 8‑bit = 256 colours).
  • File size = width × height × colour‑depth ÷ 8 (bytes).

• Vector – stores geometric primitives (lines, curves). Size depends on number of objects, not resolution.

Sound

• Sampling rate (samples / second) – e.g. 44.1 kHz for CD quality.
• Bit depth – e.g. 16‑bit gives 65 536 amplitude levels.
• File size = sampling‑rate × bit‑depth × channels × duration ÷ 8.

2.7 Data compression

• Lossless – exact reconstruction.

  • Run‑Length Encoding (RLE): replace consecutive identical symbols with a count.
  • Huffman coding: variable‑length codes based on symbol frequencies.

• Lossy – some information discarded for higher compression.

  • JPEG – discrete cosine transform + quantisation for images.
  • MP3 – perceptual coding for audio.

2.8 Conversion exercise (example)

Convert decimal 173 to binary, octal and hexadecimal.

173 ÷ 2 = 86 r 1
86 ÷ 2 = 43 r 0
43 ÷ 2 = 21 r 1
21 ÷ 2 = 10 r 1
10 ÷ 2 = 5  r 0
5 ÷ 2  = 2  r 1
2 ÷ 2  = 1  r 0
1 ÷ 2  = 0  r 1   → binary 10101101
Octal: group binary in 3‑bit blocks → 101 011 101 → 5 3 5 → 0o535
Hexadecimal: group in 4‑bit blocks → 1010 1101 → A D → 0xAD

3. Communication & Networking

3.1 Network topologies

3.2 LAN vs WAN

• LAN (Local Area Network) – limited to a single building or campus; high bandwidth (≥100 Mbps), low latency, usually Ethernet or Wi‑Fi.
• WAN (Wide Area Network) – spans cities, countries, or the globe; lower bandwidth, higher latency; uses technologies such as MPLS, leased lines, satellite.

3.3 Network models

• Client‑server – dedicated servers provide resources to many clients (e.g. web server + browsers).
• Peer‑to‑peer (P2P) – each node can act as both client and server (e.g. file‑sharing networks).

3.4 OSI and TCP/IP layers (summary)

3.5 Common protocols per TCP/IP layer

3.6 IP addressing and subnetting

• IPv4 – 32‑bit address written as dotted decimal, e.g. 192.168.1.10.
• Subnet mask separates network and host portions; e.g. 255.255.255.0 gives a /24 network.
• IPv6 – 128‑bit address written in hexadecimal groups, e.g. 2001:0db8:85a3::8a2e:0370:7334.

3.7 DNS – the “phone‑book” of the Internet

Domain Name System translates a host name (e.g. www.example.com) to an IP address. Typical resolution steps:

1. Client checks local cache.
2. If not found, query the configured recursive resolver.
3. Resolver contacts authoritative name servers and returns the IP.

3.8 Ethernet & CSMA‑CD

• Ethernet frames contain destination/source MAC, type, payload, CRC.
• CSMA‑CD (Carrier Sense Multiple Access with Collision Detection) – stations listen before transmitting; if a collision is detected, they wait a random back‑off time.

3.9 Wireless networking (Wi‑Fi, Bluetooth)

• Uses CSMA‑CA (Collision Avoidance) instead of detection.
• Common standards: 802.11a/b/g/n/ac – differ in frequency, data rate, range.

3.10 Cloud computing basics

• Delivery of computing resources (servers, storage, applications) over the Internet.
• Service models: IaaS, PaaS, SaaS.
• Advantages: scalability, pay‑as‑you‑go; concerns: security, vendor lock‑in.

3.11 Sample networking pseudocode – simple routing decision

INPUT packetDestinationIP
IF packetDestinationIP STARTS WITH "192.168." THEN
SET nextHop ← "Router_A"
ELSE IF packetDestinationIP STARTS WITH "10." THEN
SET nextHop ← "Router_B"
ELSE
SET nextHop ← "Default_Gateway"
END IF
OUTPUT nextHop

4. Hardware Fundamentals

4.1 Von Neumann architecture

Four main components:

1. CPU – Control Unit + ALU.
2. Memory – Stores program and data (RAM).
3. I/O – Devices for input and output.
4. Bus system – Path for data, addresses and control signals.

Program stored in memory → fetched → decoded → executed (fetch‑decode‑execute cycle).

4.2 Core components (summary table)

4.3 Logic gates and truth tables

Basic gates used to build combinational circuits.

4.4 Combinational vs. sequential circuits

• Combinational – output depends only on current inputs (e.g. adders, multiplexers).
• Sequential – output depends on inputs and stored state (e.g. flip‑flops, counters).

5. Processor Fundamentals

5.1 Simple instruction set (assembly‑like)

LOAD   R1, address      ; R1 ← Memory[address]
ADD    R1, R2           ; R1 ← R1 + R2
STORE  R1, address      ; Memory[address] ← R1
JUMP   label            ; PC ← address of label
CMP    R1, R2           ; set condition flags
BRANCHIFZERO label   ; PC ← label if zero flag set

5.2 Addressing modes

• Immediate – operand is part of the instruction (e.g. ADD R1, #5).
• Direct – address field gives the memory location.
• Indirect – address field points to a memory location that contains the real address.
• Indexed – effective address = base address + index register (useful for arrays).

5.3 Bit‑wise operations and masking

mask ← 0b00001111          ; isolate lower 4 bits
result ← value AND mask    ; keep only those bits

5.4 Shift operations

• Logical shift – inserts zeros (used for unsigned numbers).
• Arithmetic shift – preserves sign bit for signed numbers.

5.5 Mini‑exercise

Given value = 0b10110110, what is the result after value >> 2?

10110110 >> 2 → 00101101 (binary) → 45 (decimal)

6. System Software

6.1 Operating system responsibilities

• Process management – creation, scheduling, termination.
• Memory management – allocation, paging, segmentation, virtual memory.
• File system – hierarchical storage, permissions, directory handling.
• Device control – drivers abstract hardware, I/O buffering.
• Security – authentication, access control, auditing.

6.2 Process scheduling

• Pre‑emptive multitasking – OS can interrupt a running process.
• Non‑pre‑emptive (co‑operative) – process yields control voluntarily.
• Common algorithms:

  • Round‑Robin (time‑slice)
  • Shortest‑Job‑First (SJF)
  • Priority‑based
  • Multilevel feedback queue

6.3 Memory management techniques

• Paging – fixed‑size pages, page tables, page‑fault handling.
• Segmentation – variable‑size logical segments (code, data, stack).
• Virtual memory – allows programs to use more memory than physically available.

6.4 Language translators

6.5 Scenario question

“A computer runs several background services. Explain how the OS decides which service gets CPU time, and name two scheduling algorithms that could be used.”

• The scheduler examines each ready process, assigns a time‑slice (or priority), and may pre‑empt the current process based on the chosen algorithm.
• Possible algorithms: Round‑Robin, Shortest‑Job‑First, Priority‑based.

7. Security & Privacy

7.1 Symmetric encryption

• Same key for encryption and decryption (e.g. AES, DES).
• Fast, suitable for bulk data.
• Key distribution is the main challenge.

7.2 Asymmetric encryption

• Public‑key pair – public key encrypts, private key decrypts (e.g. RSA, ECC).
• Used for secure key exchange, digital signatures, authentication.

7.3 Simple Caesar cipher (example code)

FUNCTION caesarEncrypt(text, shift)
FOR each character c IN text DO
IF c IS a letter THEN
base ← ASCII('A') IF c IS uppercase ELSE ASCII('a')
c ← CHAR( ( (ASCII(c) - base + shift) MOD 26 ) + base )
END IF
END FOR
RETURN text
END FUNCTION

7.4 Hash functions and data integrity

• One‑way functions that produce a fixed‑size digest (e.g. MD5, SHA‑256).
• Used for password storage, file verification, digital signatures.

7.5 Public Key Infrastructure (PKI)

• Certificates bind a public key to an entity, signed by a trusted Certificate Authority.
• Ensures authenticity and enables encrypted communication over insecure networks.

7.6 Privacy principles (relevant to GDPR)

• Data minimisation – collect only what is necessary.
• Encryption at rest and in transit.
• Right to access, rectification, erasure.
• Accountability – organisations must demonstrate compliance.

8. Ethics & Intellectual Property

8.1 Copyright, patents, trademarks and licences

• Copyright – exclusive right to reproduce, distribute, adapt.
• Patents – protect inventions for 20 years.
• Trademarks – protect brand identifiers.
• Software licences:

  • GNU GPL – copyleft, any derivative must also be GPL.
  • MIT – permissive, minimal restrictions.
  • Creative Commons (CC‑BY, CC‑BY‑SA, etc.) – for non‑code works.

8.2 Ethical dilemmas

Discussion prompts (use in classroom debates):

• “Should universities allow students to submit AI‑generated code for assessments? Consider fairness, learning outcomes and academic integrity.”
• “Is it ethical for companies to sell anonymised user data for targeted advertising?”
• “What responsibilities do developers have when creating autonomous systems (e.g., self‑driving cars)?”

8.3 Professional codes of conduct

• ACM Code of Ethics – public interest, privacy, honesty.
• BCS Code of Conduct – competence, duty to society, respect for intellectual property.

9. Databases

9.1 Relational model basics

• Tables (relations) consist of rows (records) and columns (fields).
• Primary key – uniquely identifies each record.
• Foreign key – creates a relationship between tables.
• Normalization – organising data to reduce redundancy (1NF, 2NF, 3NF).

9.2 Simple ER‑diagram example

Entities: Student (StudentID PK, Name, DOB) and Enrollment (EnrollID PK, StudentID FK, CourseCode).

9.3 Basic SQL snippets

-- Create tables
CREATE TABLE Student (
StudentID   INT PRIMARY KEY,
Name        VARCHAR(50),
DOB         DATE
);
CREATE TABLE Enrollment (
EnrollID    INT PRIMARY KEY,
StudentID   INT REFERENCES Student(StudentID),
CourseCode  VARCHAR(10)
);
-- Insert a record
INSERT INTO Student (StudentID, Name, DOB)
VALUES (101, 'Alice Brown', '2003-04-12');
-- Retrieve students enrolled in a specific course
SELECT S.Name, S.DOB
FROM Student S
JOIN Enrollment E ON S.StudentID = E.StudentID
WHERE E.CourseCode = 'CS101';
-- Update a student's name
UPDATE Student SET Name = 'Alice B.' WHERE StudentID = 101;
-- Delete a course enrolment
DELETE FROM Enrollment WHERE EnrollID = 5;

9.4 Data integrity constraints

• NOT NULL – column must contain a value.
• UNIQUE – all values in the column must be distinct.
• CHECK – enforces a condition (e.g. CHECK (Mark BETWEEN