One handout per topic, in plain English. Read the handout before the textbook, not after it — each one takes about five minutes and is designed to make the idea land first, so the formal version has somewhere to stick.
20 handoutsCambridge AS & A LevelPrintableFree to copy and share
Everything a computer stores is a number in binary — the only question is what rule you use to read it back.
Picture itThe pattern 11000001 could be the number 193, or the number −63, or the character Á, or a shade of red. Nothing in the bits themselves tells you which. The interpretation lives in the program, not in the memory. That is the single most important idea in this topic.
Bases and conversions, by hand
No calculators are allowed in any 9618 paper, so binary–denary–hexadecimal conversion must be automatic. Denary to binary: repeatedly divide by 2 and read the remainders upwards, or subtract descending powers of two. Binary to hex: split into groups of four from the right.
Binary Coded Decimal
BCD stores each decimal digit in its own four bits, so 59 becomes 0101 1001. It wastes space and complicates arithmetic, but it converts to a display trivially and avoids rounding — which is why it appears in calculators, digital clocks and financial systems.
Two's complement and overflow
Negate by flipping every bit and adding one. Addition needs no special rules. Overflow occurs when the result will not fit in the available bits — in 8-bit two's complement, adding two positives to get a negative sign bit is the tell-tale sign.
Character sets
ASCII uses 7 bits for 128 characters; extended ASCII uses 8 for 256. Unicode uses more bits per character to cover every writing system, at the cost of larger files. UTF-8 is variable-length precisely to keep ASCII text small.
Images, sound and compression
Bitmap files store a pixel grid — file size ≈ resolution × colour depth, plus a header holding dimensions and depth. Vector files store drawing instructions and scale without loss. Sound is sampled: sample rate × resolution × duration gives the file size. Run-length encoding is the lossless method you must be able to perform.
The bit that catches people outThe header of a bitmap file is not padding. It stores the width, height and colour depth — without it, the string of pixel values is unreadable, because nothing else says where each row ends.
The grown-up words
What it means
What it is called
Note
Storing each decimal digit in four bits
binary coded decimal
Used in displays and finance
Representing negatives by flipping and adding 1
two's complement
Addition works normally
Result too large for the available bits
overflow
Detect via the sign bit
7-bit character set of 128 characters
ASCII
Extended ASCII uses 8 bits
Character set covering all writing systems
Unicode
More bits per character
Image stored as a grid of pixels
bitmap
Loses quality when scaled
Image stored as drawing instructions
vector graphic
Scales without loss
Lossless method storing repeats as counts
run-length encoding
Poor on noisy data
Check you have got it
Convert denary 214 to 8-bit binary and to hexadecimal.
11010110 and D6. 128+64+16+4+2 = 214; split as 1101 (D) and 0110 (6).
Why is run-length encoding a poor choice for a photograph?
Photographs rarely contain long runs of identical pixel values, so the encoded file can end up larger than the original.
Edvia Free Resources · Computer Science 9618 · Topic 1 — free to copy and share
Topic 2
Communication
Once more than one computer is involved, most of the difficulty stops being computation and becomes agreement.
Picture itTwo people with tin cans and a string can talk. Two hundred people cannot — you need addresses, a way to take turns, rules about who speaks when, and a way to notice when a message arrived garbled. Networking is almost entirely those rules.
LAN, WAN and topologies
A LAN covers one site and is owned by the organisation; a WAN spans sites and uses third-party infrastructure. Star topology puts every device on its own link to a central switch — resilient, and a fault affects one device. Bus shares one backbone — cheap, but a break stops everything.
Hardware, and what each device actually does
A hub broadcasts to every port. A switch learns MAC addresses and sends frames only to the right port. A router connects different networks and forwards by IP address. A NIC gives a device its MAC address. Confusing hub, switch and router is the classic lost mark.
Wired versus wireless
Copper cable is cheap; fibre is faster over long distances, immune to electrical interference and harder to tap. Wireless (Wi-Fi, Bluetooth) trades speed and security for mobility — Bluetooth for short-range low-bandwidth pairing, Wi-Fi for general network access.
Client–server, peer-to-peer and the cloud
Client–server centralises control, backup and security but has a single point of failure. Peer-to-peer shares resources with no central authority — resilient, harder to manage. Cloud computing gives scalability and remote access, at the cost of depending on a provider and a connection.
The internet's addressing
IPv4 gives about 4.3 billion addresses and has run out; IPv6 uses 128 bits. Public addresses are routable on the internet, private ones are not and are translated at the router. DNS resolves names to addresses, working up a hierarchy of servers until one knows the answer.
The bit that catches people outA MAC address identifies the hardware and does not change as a packet crosses networks. An IP address identifies the device's current position on a network and is reassigned as it moves. Both are addresses; they answer different questions.
The grown-up words
What it means
What it is called
Note
Network confined to one site
LAN
Owned by the organisation
Network spanning distant sites
WAN
Uses third-party links
Device sending frames only to the right port
switch
A hub broadcasts to all
Device connecting different networks
router
Forwards by IP address
Hardware address fixed to the network card
MAC address
Does not change
Model with a central controlling computer
client-server
Single point of failure
Model with equal computers sharing resources
peer-to-peer
No central authority
System resolving names to IP addresses
DNS
Hierarchical lookup
Check you have got it
Give one advantage of a switch over a hub.
A switch sends each frame only to the port of the destination device, reducing unnecessary traffic and collisions and improving security, whereas a hub broadcasts to every port.
Why was IPv6 introduced?
IPv4's 32-bit addresses give about 4.3 billion combinations, which have been exhausted. IPv6 uses 128 bits, providing a practically unlimited address space.
Edvia Free Resources · Computer Science 9618 · Topic 2 — free to copy and share
Topic 3
Hardware
The logic that makes a processor work is built from a handful of gates, and the memory it uses is a hierarchy of compromises.
Picture itA row of light switches wired so that the lamp only lights under one exact combination. Stack a few million of those and you have an arithmetic unit. Nothing in a processor is magic — it is gates, arranged very carefully, running very fast.
Gates, truth tables and circuits
NOT, AND, OR, NAND, NOR and XOR. Build a truth table with 2ⁿ rows for n inputs, listing combinations in strict counting order, and add a column for every intermediate gate output. Never jump from inputs to the final output in one step.
Karnaugh maps simplify expressions
A K-map is a truth table rearranged so that adjacent cells differ by exactly one variable — Gray code ordering. Group the 1s into rectangles of 1, 2, 4 or 8, as large as possible, and read off the variables that stay constant in each group. Groups may overlap and may wrap around the edges.
Half adders and full adders
A half adder adds two bits, giving sum (XOR) and carry (AND). A full adder also takes a carry in, so full adders can be chained to add multi-bit numbers. This is where the ALU's arithmetic physically comes from.
Flip-flops store a bit
An SR flip-flop holds a state, with S = R = 1 as its invalid input. A JK flip-flop fixes that by making the forbidden combination toggle instead. Flip-flops are the basis of registers and of static RAM.
Storage and the memory hierarchy
Registers are fastest and tiniest; then cache; then RAM; then secondary storage; then offline archive. Speed falls and capacity rises at every step down. Magnetic, optical and solid-state storage differ in cost per gigabyte, speed, durability and whether they have moving parts.
The bit that catches people outIn a K-map, groups must be rectangles of a power of two — 1, 2, 4, 8 — and bigger groups mean simpler expressions. A group of three is not allowed, and grouping too timidly gives a technically correct but unsimplified answer that loses the mark.
The grown-up words
What it means
What it is called
Note
Output 1 only when inputs differ
XOR gate
Used in the half adder
Grid for simplifying Boolean expressions
Karnaugh map
Gray code ordering
Adjacent codes differ by one bit
Gray code
Makes K-map grouping valid
Circuit adding two bits
half adder
Sum and carry out
Adder that also accepts a carry in
full adder
Chained for multi-bit addition
Circuit storing one bit
flip-flop
SR and JK types
Fastest, smallest storage in the CPU
register
Top of the hierarchy
Storage with no moving parts
solid-state
Fast, durable, costlier
Check you have got it
How many rows does a truth table with four inputs have?
Sixteen — 2⁴, because each of the four inputs can independently be 0 or 1.
Why must a Karnaugh map use Gray code ordering along its axes?
So that horizontally and vertically adjacent cells differ in exactly one variable, which is what makes grouping them valid for simplification.
Edvia Free Resources · Computer Science 9618 · Topic 3 — free to copy and share
Topic 4
Processor fundamentals
A processor does one very simple thing over and over: fetch an instruction, work out what it means, and do it.
Picture itA clerk with a tiny desk and a very long list of instructions in a filing cabinet. He fetches instruction number 1, does it, moves the marker to 2, fetches that, and so on. A jump instruction just moves the marker somewhere else. That marker is the program counter, and it is the whole story of control flow.
The registers and what each holds
PC — address of the next instruction. MAR — the address being accessed. MDR — the data or instruction fetched. CIR — the current instruction being decoded. ACC — the working result. IX — the index register for indexed addressing. SR — the status register's flags.
The fetch–execute cycle in register transfer notation
MAR ← [PC]; PC ← [PC] + 1; MDR ← [[MAR]]; CIR ← [MDR]. Then decode and execute. Square brackets mean 'contents of', so [[MAR]] is the contents of the address held in MAR. Writing this notation correctly is an exam skill in its own right.
Buses and how they limit performance
The address bus is unidirectional; its width sets the maximum addressable memory (n lines address 2ⁿ locations). The data bus is bidirectional; its width sets how much data moves per transfer. The control bus carries read/write and timing signals.
Interrupts
A device raises an interrupt. At the end of the current cycle the processor checks the interrupt register, saves its state onto the stack, runs the interrupt service routine, then restores the state and resumes. Priorities decide which of several competing interrupts is served first.
Assembly language and addressing modes
Immediate — the operand is the value itself. Direct — the operand is an address. Indirect — the address holds another address. Indexed — add the index register to the address. Relative — offset from the current position. Tracing an assembly program by hand, with a trace table, is a standard Paper 1 question.
The bit that catches people outThe program counter is incremented during the fetch, before the instruction is executed. That is why a jump instruction has to overwrite the PC rather than adjust it — the PC is already pointing at the following instruction by the time the jump runs.
The grown-up words
What it means
What it is called
Note
Holds the address of the next instruction
program counter
Incremented during fetch
Holds the address currently being accessed
memory address register
Uses the address bus
Holds the instruction being decoded
current instruction register
After the fetch
Holds intermediate arithmetic results
accumulator
Used by the ALU
Notation using square brackets for contents
register transfer notation
MAR <- [PC]
Signal asking the processor for attention
interrupt
Handled by an ISR
Operand is the value itself
immediate addressing
No memory lookup
Address held at the given address
indirect addressing
Two lookups
Check you have got it
An address bus has 20 lines. How many memory locations can be addressed?
2²⁰ = 1 048 576 locations (1 MiB if each location is a byte).
Why is the processor's state saved before an interrupt service routine runs?
So that the interrupted program can be resumed exactly where it left off, with the same register contents, once the ISR has finished.
Edvia Free Resources · Computer Science 9618 · Topic 4 — free to copy and share
Topic 5
System software
The operating system is the layer that stops every program from having to know about every piece of hardware.
Picture itAn office manager. Programs ask for 'a file' or 'the printer' and never learn what brand of disk or printer is installed. The manager also decides who gets the desk next, stops two people writing on the same page at once, and cleans up after everyone.
What the operating system manages
Processes, memory, files, input/output devices, security and the user interface. Every one of these exists because sharing a machine between programs creates conflicts that somebody has to arbitrate.
Scheduling shares the processor
First come first served is simple but a long job blocks everything. Shortest job first minimises average waiting but can starve long jobs. Round robin gives each process a time slice, so response is fair. Shortest remaining time preempts. Each is a different answer to the same fairness-versus-throughput trade-off.
Memory management and paging
Paging divides memory into fixed-size pages, segmentation into variable-size logical segments. Virtual memory keeps unused pages on disk and swaps them in when needed. Too little RAM causes disk thrashing — the machine spends more time swapping than working.
Utilities and the software layers
Utility software includes disk formatters, defragmenters, backup tools, file compression and anti-virus. Between hardware and the user sit firmware, the operating system, utilities, and finally applications — a layered stack where each level only talks to its neighbours.
Translators
An assembler converts assembly to machine code. A compiler translates a whole program, reporting all errors, producing an executable. An interpreter translates line by line and stops at the first error. Compilation runs in stages: lexical analysis, syntax analysis, semantic analysis, code generation and optimisation.
The bit that catches people outAdding more virtual memory does not have the same effect as adding more RAM. Virtual memory prevents a program failing for lack of space, but disk access is orders of magnitude slower — beyond a point the machine slows down rather than speeding up.
The grown-up words
What it means
What it is called
Note
Software managing hardware and processes
operating system
Between hardware and apps
Deciding which process uses the CPU next
scheduling
Round robin, SJF, FCFS
Fixed-size divisions of memory
paging
Segmentation uses variable sizes
Using disk space as extra RAM
virtual memory
Much slower than RAM
Excessive swapping between RAM and disk
disk thrashing
Symptom of too little RAM
Converts assembly to machine code
assembler
One-to-one translation
Translates the whole program at once
compiler
Produces an executable
First stage of compilation
lexical analysis
Produces tokens
Check you have got it
Give one advantage and one disadvantage of round robin scheduling.
Advantage: every process gets CPU time regularly, so response times are fair and no process is starved. Disadvantage: frequent context switching adds overhead, and it ignores how urgent or short a job is.
Why does an interpreter make debugging easier than a compiler?
It translates and executes line by line, halting at the first error with its exact location, so a fault can be found and fixed immediately without recompiling the whole program.
Edvia Free Resources · Computer Science 9618 · Topic 5 — free to copy and share
Topic 6
Security, privacy and data integrity
Keeping data safe means three separate things — stopping it being stolen, stopping it being lost, and stopping it being wrong.
Picture itA shop. A lock on the door stops theft (security). A second set of keys with a friend means you can get back in if yours are lost (backup). A careful stock count means the numbers on the shelf match the numbers in the book (integrity). Doing one of the three well and ignoring the others still leaves you in trouble.
Threats and countermeasures
Malware, phishing, pharming, brute-force attacks, DDoS, SQL injection, data interception. Countermeasures: firewalls, anti-malware, strong passwords and two-factor authentication, encryption, access levels, patching, and staff training — because most successful attacks exploit people, not code.
Encryption, symmetric and asymmetric
Symmetric uses one shared key: fast, but distributing the key securely is the problem. Asymmetric uses a public key to encrypt and a private key to decrypt. In practice systems combine them — asymmetric to exchange a symmetric session key, then symmetric for speed.
Digital signatures and certificates
A message is hashed to a digest, which the sender encrypts with their private key. The recipient decrypts it with the sender's public key and recomputes the hash: matching digests prove both the sender's identity and that nothing was altered. A certificate from a certificate authority vouches that a public key really belongs to who it claims.
Data integrity checks
Parity, checksums, check digits, echo check and ARQ detect transmission errors. Validation (range, format, length, presence, type, check digit) and verification (double entry, visual check) protect data at entry.
Backups and privacy
Full, incremental and differential backups differ in what they copy and how long restoring takes. Backups must be stored off-site, and tested. Privacy is separate from security: it concerns what data you are entitled to collect and keep at all, not just whether you protect it.
The bit that catches people outEncryption protects confidentiality, not integrity. Encrypted data can still be corrupted or replaced. It is the hash and the digital signature that prove nothing changed on the way — different problem, different tool.
The grown-up words
What it means
What it is called
Note
Keeping data secret from unauthorised people
confidentiality
Encryption's job
Data being correct and unaltered
integrity
Hashes and checksums
One shared key for both directions
symmetric encryption
Key distribution is hard
Public key encrypts, private key decrypts
asymmetric encryption
Solves key distribution
Fixed-length summary of a message
digest
Produced by a hash function
Encrypted digest proving sender and integrity
digital signature
Uses the private key
Third party vouching for a public key
certificate authority
Issues certificates
Backup copying only what changed since the last one
incremental backup
Fast to make, slow to restore
Check you have got it
Why do real systems use asymmetric encryption to exchange a symmetric key rather than using asymmetric encryption throughout?
Asymmetric encryption is computationally slow. Using it only to exchange a session key gets the secure key distribution, then symmetric encryption handles the bulk data quickly.
A digital signature verifies as valid. What two things does that prove?
That the message came from the holder of the matching private key (authenticity) and that it has not been altered since signing (integrity).
Edvia Free Resources · Computer Science 9618 · Topic 6 — free to copy and share
Topic 7
Ethics and ownership
Some questions in computing have no technical answer — the code will run either way, and the decision is about what should be done.
Picture itYou can write a program that scrapes every public post someone ever made and builds a profile of them. Nothing in the compiler will object. Whether you should is a different kind of question entirely, and it is one this syllabus expects you to argue rather than dodge.
Professional codes of conduct
The ACM and BCS codes set out duties: act in the public interest, maintain competence, be honest about your abilities, respect confidentiality, avoid conflicts of interest, and do not claim work that is not yours. These are professional obligations, not vague good intentions.
Copyright, patents and licensing
Copyright protects the expression of an idea — the source code — automatically. A patent protects an invention or process and must be applied for. A trademark protects a name or logo. Software is licensed, not sold, and the licence sets what you may do with it.
Free, open-source and proprietary
Free software guarantees freedom to run, study, modify and redistribute. Open source makes the source available, sometimes under weaker conditions. Proprietary software keeps the source closed. The trade-offs are support, security auditing, cost and control — and reasonable people weigh them differently.
Privacy and data protection
Collecting personal data brings duties: collect only what is needed, keep it accurate, keep it secure, keep it only as long as necessary, and be honest about what you hold. Data about children carries additional obligations in nearly every jurisdiction.
Artificial intelligence raises new questions
Who is accountable when an automated system causes harm? What happens when training data carries historic bias? Should a system that affects someone's life be required to explain its decision? The exam wants a reasoned position with evidence, not a list of worries.
The bit that catches people out"It is legal" and "it is ethical" are different claims, and an answer that only addresses one of them is only half an answer. Plenty of legal data collection is ethically questionable, and the syllabus expects you to say why.
The grown-up words
What it means
What it is called
Note
Automatic protection of an original expression
copyright
Covers source code
Protection of an invention, applied for
patent
Covers a process
Protection of a name or logo
trademark
Brand identity
Agreement setting how software may be used
licence
Software is licensed, not sold
Freedom to run, study, modify, redistribute
free software
Beyond just visible source
Source code available for inspection
open source
Enables community auditing
Closed-source commercial software
proprietary software
Vendor controls changes
Professional rules for computing practitioners
code of conduct
ACM and BCS
Check you have got it
Distinguish between copyright and a patent as they apply to software.
Copyright applies automatically and protects the particular expression — the actual source code written. A patent must be applied for and protects an invention or process, so it could cover the underlying method regardless of how it is coded.
Give one argument for and one against releasing security software as open source.
For: anyone can inspect the code, so vulnerabilities are more likely to be found and fixed. Against: attackers can also inspect it and search for flaws before maintainers patch them.
Edvia Free Resources · Computer Science 9618 · Topic 7 — free to copy and share
Topic 8
Databases
A well-designed database stores each fact exactly once, so it cannot contradict itself — and normalisation is the process that gets you there.
Picture itA club keeps a spreadsheet with each member's phone number typed next to every event they attended. One member changes number, three rows get updated, four do not. Now the database holds two answers to one question, and no rule to decide between them. Normalisation exists to make that situation impossible.
The relational vocabulary
An entity is a thing the database stores data about; an attribute is a property of it; a tuple is one record. A primary key uniquely identifies a tuple; a composite key uses more than one attribute; a foreign key references another table's primary key; a secondary key supports fast searching.
Normalisation to 3NF
1NF: no repeating groups; every attribute atomic. 2NF: in 1NF, and no partial dependency on part of a composite key. 3NF: in 2NF, and no non-key attribute depends on another non-key attribute. The result: every fact stored once, so update, insert and delete anomalies vanish.
Entity-relationship modelling
Relationships are one-to-one, one-to-many or many-to-many. A many-to-many relationship cannot be implemented directly — it is resolved with a link table holding the two foreign keys, which typically form a composite primary key.
The DBMS and its tools
A DBMS provides a data dictionary, a query processor, developer interface and security controls. DDL (CREATE, ALTER, DROP) defines structure; DML (SELECT, INSERT, UPDATE, DELETE) manipulates data. Views give different users a restricted picture of the same data.
SQL you must be able to write
SELECT with WHERE, ORDER BY, and joins across tables; aggregate functions COUNT, SUM, AVG, MIN, MAX with GROUP BY; INSERT INTO, UPDATE ... SET, DELETE FROM; and CREATE TABLE with data types and a PRIMARY KEY constraint.
The bit that catches people outNormalisation is not always the finishing line. Highly normalised databases need more joins, which can be slower — real systems sometimes deliberately denormalise for performance. The exam wants 3NF, but knowing why someone might not go there is a stronger answer.
The grown-up words
What it means
What it is called
Note
A thing the database stores data about
entity
Becomes a table
Property of an entity
attribute
Becomes a field
Key made of more than one attribute
composite key
Common in link tables
Attribute referencing another table's key
foreign key
Creates the relationship
Every attribute atomic, no repeating groups
first normal form
1NF
No partial dependency on part of a key
second normal form
2NF
No non-key attribute depends on another
third normal form
3NF
Table resolving a many-to-many relationship
link table
Holds two foreign keys
Language defining database structure
DDL
CREATE, ALTER, DROP
Check you have got it
Why can a many-to-many relationship not be implemented directly in a relational database?
Neither table could hold a single foreign key value pointing at many rows in the other. A link table is created holding a foreign key to each side, turning it into two one-to-many relationships.
A table is in 2NF but a non-key attribute depends on another non-key attribute. What normal form is violated, and how is it fixed?
Third normal form. Move the dependent attributes into a separate table, leaving a foreign key behind in the original.
Edvia Free Resources · Computer Science 9618 · Topic 8 — free to copy and share
Topic 9
Algorithm design and problem-solving
The hard part of programming is deciding exactly what should happen — the code is what you write once you already know.
Picture itExplaining to somebody who will do precisely what you say and nothing more how to make a cup of tea. You will discover within three sentences that you have been leaving out steps your whole life. That discovery, made on paper before you touch a compiler, is what algorithm design is for.
Decomposition, abstraction, structure charts
Break the problem into sub-problems and keep going until each piece can be written directly. Abstraction means keeping what matters and discarding what does not. A structure chart shows the hierarchy of modules and the data passed between them.
Pseudocode and the standard constructs
Sequence; selection with IF and CASE; iteration with FOR (count-controlled), WHILE (pre-condition) and REPEAT UNTIL (post-condition). Write pseudocode consistently — the 9618 style guide has a defined form, and using it costs nothing and prevents ambiguity.
Standard algorithms
Linear search (unsorted, O(n)). Binary search (sorted, halves the range each time, O(log n)). Bubble sort (repeated adjacent swaps, with an optimisation to stop early when a pass makes no swaps). Insertion sort (each item placed into the sorted part). Know how each behaves as data grows.
Stepwise refinement
Start with the top-level statement of what happens, then expand each step into more detail, repeatedly, until every line could be written as code. This makes large problems tractable and makes the eventual program's structure follow the problem's structure.
Testing and trace tables
Test with normal, abnormal, extreme and boundary data. A trace table has a column per variable and a row per iteration, showing exactly what the program does — it is how you find a logic error that produces no error message at all.
The bit that catches people outBinary search requires sorted data. If a question gives you an unsorted list and asks for the fastest search, the honest answer is that you must either sort first — which costs time — or accept a linear search. Applying binary search to unsorted data simply gives wrong answers.
The grown-up words
What it means
What it is called
Note
Breaking a problem into sub-problems
decomposition
Repeat until codeable
Discarding irrelevant detail
abstraction
Keeps the model manageable
Diagram of modules and data passed
structure chart
Shows the hierarchy
Expanding each step into more detail
stepwise refinement
Top-down design
Search checking each item in turn
linear search
Works on unsorted data
Search halving a sorted range each time
binary search
Requires sorted data
Sort using repeated adjacent swaps
bubble sort
Stop early if no swaps
Table of variable values per iteration
trace table
Finds logic errors
Check you have got it
How many comparisons does a binary search need at most on 1000 sorted items?
Ten, because each comparison halves the range and 2¹⁰ = 1024, which is the first power of two above 1000.
Give an example each of extreme and abnormal test data for a field accepting exam marks 0–100.
Extreme: 0 and 100 — the largest and smallest valid values. Abnormal: −5, 150 or 'seventy' — values that must be rejected.
Edvia Free Resources · Computer Science 9618 · Topic 9 — free to copy and share
Topic 10
Data types and structures
Choosing how to store your data decides what your program can do quickly — and what it will be painfully slow at.
Picture itA queue at a shop, a stack of plates, and a filing tree. Adding to the end of a queue is easy; taking from the middle is not. Taking the top plate is easy; taking the bottom is not. Every data structure is fast at some operations and bad at others, and picking the right one is most of the design.
Files and records
Serial files append in arrival order. Sequential files are ordered by a key. Random-access files use a hashing algorithm on the key to compute a position, giving direct access — with collisions handled by overflow areas or probing.
Stacks and queues
A stack is last in, first out, with a single stack pointer — used for procedure calls, undo and expression evaluation. A queue is first in, first out with head and tail pointers; a circular queue reuses freed space by wrapping the pointers round. You must be able to code push, pop, enqueue and dequeue, including full and empty checks.
Linked lists
Each node holds data and a pointer to the next. Insertion and deletion are cheap — change a pointer — but access is sequential, so finding the tenth item means walking there. A free list tracks unused nodes.
Binary trees
Each node has left and right pointers. In a binary search tree, everything smaller sits left and everything larger right, so searching an approximately balanced tree is O(log n). Traversals: in-order gives sorted output, pre-order and post-order are used for copying and evaluating.
Abstract data types
An ADT is defined by the operations it offers, not by how it is stored. A stack is a stack whether it is built on an array or a linked list. Separating the interface from the implementation is what lets you change one without breaking the other.
The bit that catches people outA binary search tree only gives O(log n) performance if it is reasonably balanced. Insert already-sorted data and every node goes down one side — the tree degenerates into a linked list and searching becomes O(n).
The grown-up words
What it means
What it is called
Note
Last in, first out structure
stack
One stack pointer
First in, first out structure
queue
Head and tail pointers
Queue reusing space by wrapping round
circular queue
Avoids drift
Nodes joined by pointers
linked list
Cheap insert, sequential access
Structure with left and right child pointers
binary tree
Search tree if ordered
Traversal producing sorted output
in-order traversal
Left, node, right
Computing a storage position from a key
hashing algorithm
Enables direct access
Two keys hashing to the same position
collision
Handled by overflow or probing
Structure defined by its operations
abstract data type
Implementation hidden
Check you have got it
Why is inserting into the middle of a linked list cheaper than into the middle of an array?
Only two pointers need changing. In an array every subsequent element must be shifted along to make room.
What traversal of a binary search tree outputs the data in ascending order?
In-order traversal — visit the left subtree, then the node, then the right subtree.
Edvia Free Resources · Computer Science 9618 · Topic 10 — free to copy and share
Topic 11
Programming
Turning an algorithm into working code is mostly about being precise, and about breaking the work into pieces small enough to test.
Picture itA recipe written for a cook who cannot improvise. Every quantity must be stated, every step ordered, and every ingredient must exist before you refer to it. The reward for that precision is that once it works, it works identically every time.
Data types and declarations
INTEGER, REAL, CHAR, STRING, BOOLEAN, DATE. Declare variables before use and choose the type deliberately — a leading zero, a decimal fraction or a value used in arithmetic all point at different choices.
Arrays and records
One- and two-dimensional arrays are indexed collections of the same type. A record (user-defined type) groups different types under one name — one Student with a name, a mark and a date. An array of records is the standard structure for a table of data.
Procedures, functions, parameters
A procedure performs a task; a function returns a value. Parameters can be passed by value (a copy — changes do not affect the caller) or by reference (the original — changes do). Knowing which your language uses for arrays matters more than it sounds.
Scope and local versus global
A local variable exists only inside its subroutine and is destroyed when it returns. A global variable is visible everywhere, which makes programs harder to debug because any part of the code could have changed it. Prefer local variables and parameters.
String handling and file operations
Common operations: length, substring, position, concatenation, upper and lower case, and conversion between strings and numbers. Files are opened for READ, WRITE or APPEND, processed line by line, and — the step people forget — closed.
The bit that catches people outPassing a parameter by value gives the subroutine a copy, so changing it inside has no effect outside. If a question asks why a procedure 'did not update the variable', by-value passing is almost always the answer.
The grown-up words
What it means
What it is called
Note
Grouping different types under one name
record
A user-defined type
Indexed collection of one type
array
One or two dimensional
Subroutine that returns a value
function
A procedure does not
Passing a copy of the argument
by value
Caller's variable unchanged
Passing the original argument
by reference
Caller's variable can change
Variable visible only in its subroutine
local variable
Destroyed on return
Variable visible everywhere
global variable
Harder to debug
Adding to the end of an existing file
append mode
Does not overwrite
Check you have got it
Why are global variables generally discouraged?
Any part of the program can change them, so tracing where an incorrect value came from is difficult, and subroutines become dependent on external state rather than being self-contained and testable.
When would you use a record rather than an array?
When you need to group items of different types that describe one thing — for example a student's name (STRING), mark (INTEGER) and enrolment date (DATE).
Edvia Free Resources · Computer Science 9618 · Topic 11 — free to copy and share
Topic 12
Software development
Writing the code is one part of building software; deciding what to build, and proving it works, is the rest.
Picture itBuilding a house. Nobody starts laying bricks on day one. There is a survey, a design, a build, an inspection, and then years of repairs and extensions. Software is the same shape, and the expensive mistakes are always made at the design stage, not the coding stage.
The development life cycle
Analysis, design, coding, testing, maintenance. Whichever model you follow, these activities all happen — the models differ in how they are ordered and repeated.
Waterfall, iterative, RAD and spiral
Waterfall is sequential and well documented, but expensive to change once you have moved on. Iterative and RAD build working versions and refine them, suiting unclear requirements. Spiral adds explicit risk assessment on each loop. There is no universally best model — the right answer names the project type.
Program design tools
Structure charts, state-transition diagrams and flowcharts each show something different. A state-transition diagram lists the states a system can be in and what event moves it between them — invaluable for anything with modes.
Testing at every level
White-box testing checks internal paths; black-box testing checks inputs against expected outputs regardless of implementation. Unit testing checks one module, integration testing checks modules working together, alpha and beta testing put it in front of users, and acceptance testing confirms it meets the requirements.
Maintenance is most of the cost
Corrective maintenance fixes faults. Adaptive maintenance responds to changed environments. Perfective maintenance improves performance or usability. Over a system's lifetime, maintenance typically costs far more than the original build — which is why readable, documented code is an economic argument, not a matter of taste.
The bit that catches people outTesting cannot prove a program is correct — only that the cases you tried worked. That is why test data is chosen deliberately (normal, abnormal, extreme, boundary) rather than sampled at random.
The grown-up words
What it means
What it is called
Note
Sequential model with distinct completed stages
waterfall model
Hard to revisit
Repeated build-and-refine cycles
iterative model
Suits unclear requirements
Model adding explicit risk analysis
spiral model
Each loop reassesses risk
Diagram of states and the events between them
state-transition diagram
For mode-based systems
Testing internal code paths
white-box testing
Requires seeing the code
Testing inputs against expected outputs
black-box testing
Implementation ignored
Testing one module alone
unit testing
Before integration
Maintenance responding to a changed environment
adaptive maintenance
e.g. a new OS
Check you have got it
Why might a waterfall model be a poor choice for a project whose requirements are unclear?
Each stage is completed before the next begins, so requirements are fixed early. Discovering a misunderstanding after design is finished means expensive rework of everything downstream.
Distinguish between alpha and beta testing.
Alpha testing is done in-house by the developers' own organisation. Beta testing releases the software to a limited group of real users outside the organisation, in real conditions, before general release.
Edvia Free Resources · Computer Science 9618 · Topic 12 — free to copy and share
Topic 13
Data representation (A2)
Storing fractions in binary means trading range against precision — and you cannot have both.
Picture itA ruler that is either very long with coarse markings, or very short with fine ones. Floating-point numbers face exactly that choice: give more bits to the exponent and you can represent enormous and tiny values, but coarsely; give more to the mantissa and you get precision over a smaller range.
Fixed-point binary
A binary point at a fixed position, so places to the right are worth ½, ¼, ⅛ and so on. Simple and fast, but the range and precision are both locked in by where you put the point.
Floating-point representation
A number is stored as mantissa × 2^exponent, with both in two's complement. The mantissa sets precision, the exponent sets range. For a fixed total number of bits, giving more to one takes them from the other.
Normalisation
A normalised positive mantissa starts 0.1; a normalised negative mantissa starts 1.0. Normalising uses every available bit of the mantissa for significant digits, giving maximum precision, and makes each value's representation unique.
Rounding and truncation errors
Most decimal fractions have no exact binary representation, so values are approximated. Repeated arithmetic accumulates that error — which is why you never test two floating-point values for exact equality, and why financial systems often avoid floating point entirely.
Overflow and underflow
Overflow is a result too large for the exponent range; underflow is a non-zero result too small to represent, which collapses to zero. Both are representation failures, not arithmetic mistakes.
The bit that catches people out0.1 cannot be stored exactly in binary floating point — it recurs, just as ⅓ recurs in decimal. Adding 0.1 ten times does not reliably give exactly 1.0, which surprises people until they see why.
The grown-up words
What it means
What it is called
Note
Binary point at a fixed position
fixed-point binary
Range and precision locked
Number stored as mantissa and exponent
floating-point
Range vs precision trade-off
Part setting the precision
mantissa
More bits = finer detail
Part setting the range
exponent
More bits = bigger numbers
Adjusting so the mantissa uses all its bits
normalisation
Positive starts 0.1
Result too large to represent
overflow
Exceeds the exponent range
Non-zero result too small to represent
underflow
Collapses to zero
Error from discarding lower bits
truncation error
Accumulates with repetition
Check you have got it
Why is a floating-point number normalised?
So that every bit of the mantissa carries significant information, giving the greatest possible precision — and so each value has a single unique representation.
For a fixed 16 bits, what happens if you increase the exponent from 4 to 6 bits?
The range of representable magnitudes grows, but the mantissa shrinks from 12 to 10 bits, so precision falls — fewer significant figures per value.
Edvia Free Resources · Computer Science 9618 · Topic 13 — free to copy and share
Topic 14
Communication and internet technologies
Networking is layered on purpose, so that changing one layer does not require rewriting all the others.
Picture itPosting a parcel. You write the letter, someone else puts it in a box, someone else drives the van, someone else runs the airline. The letter-writer does not need to know the flight number, and the pilot does not read the letter. Each layer relies on the one below without knowing how it works.
Protocols and layering
The TCP/IP stack: application (HTTP, FTP, SMTP), transport (TCP, UDP), internet (IP), link. Each layer adds its own header on the way down and strips it on the way up. Layering allows a protocol at one level to be replaced without disturbing the rest.
TCP and UDP make opposite trade-offs
TCP is connection-oriented: it acknowledges, retransmits and reorders, guaranteeing delivery — right for files and web pages. UDP is connectionless with no guarantees — right for live video and voice, where a late packet is worse than a lost one.
Circuit and packet switching
Circuit switching reserves a dedicated path for the whole conversation — consistent quality, wasteful when idle. Packet switching sends packets independently by any available route — efficient and resilient, but with variable delay and out-of-order arrival.
Client–server on the web
A browser sends an HTTP request, the server returns a response. Server-side scripting runs on the server and can reach a database; client-side scripting runs in the browser and gives immediate interaction without a round trip. Validation must be repeated server-side, because client-side checks can be bypassed.
Bit streaming and bandwidth
Real-time streaming is live and cannot be paused; on-demand streaming plays stored files and buffers ahead. Buffering hides variation in network speed. Adequate bandwidth is the limiting factor, which is why quality drops rather than playback stopping.
The bit that catches people outClient-side validation is a convenience for the user, not a security measure. Anyone can disable it or send a request directly to the server, so every check that matters must be repeated on the server.
The grown-up words
What it means
What it is called
Note
Set of rules governing communication
protocol
Both ends must agree
Stack of application, transport, internet, link
TCP/IP model
Each layer adds a header
Connection-oriented, guarantees delivery
TCP
Acknowledges and retransmits
Connectionless, no delivery guarantee
UDP
Suits live audio and video
Dedicated path reserved for the call
circuit switching
Consistent but wasteful
Packets routed independently
packet switching
Efficient and resilient
Script running on the server
server-side scripting
Can access the database
Storing ahead to smooth playback
buffering
Hides network variation
Check you have got it
Why is UDP preferred to TCP for a live video call?
TCP retransmits lost packets, which arrive too late to be useful in a live call and add delay. UDP simply carries on, so a brief glitch is better than growing latency.
Give one advantage of packet switching over circuit switching.
The network is used efficiently because capacity is not reserved when idle, and packets can be rerouted around a failure, so the connection is more resilient.
Edvia Free Resources · Computer Science 9618 · Topic 14 — free to copy and share
Topic 15
Hardware and virtual machines
A processor's speed comes from doing several things at once, and a virtual machine lets one physical computer pretend to be several.
Picture itA production line. One worker doing every stage of assembly finishes one item at a time. Five workers each doing one stage, passing the item along, finish one item per step once the line is full. That is pipelining, and it is why processors are far faster than their clock speed alone suggests.
RISC and CISC
RISC: few, simple, fixed-length instructions, mostly one cycle, many registers, load–store architecture — well suited to pipelining. CISC: many complex variable-length instructions, fewer registers, more work per instruction. Modern designs borrow from both.
Pipelining and hazards
Instructions are broken into stages so several are in progress at once. Data hazards occur when an instruction needs a result not yet produced; control hazards occur at branches, where the pipeline may have to be flushed. Uniform instruction length is exactly why RISC pipelines more cleanly.
Parallel processing
Flynn's taxonomy: SISD, SIMD, MISD, MIMD. SIMD suits graphics and array work; MIMD describes multi-core general-purpose processors. Massively parallel systems chain many processors for weather modelling and similar workloads.
Interrupt handling in detail
The processor completes the current instruction, pushes the program counter and registers to the stack, jumps to the interrupt service routine via a vector table, executes it, then pops the saved state and resumes. Priority levels decide which interrupt wins when several arrive.
Virtual machines
A virtual machine is software presenting a complete simulated computer. It lets one server run several isolated systems, lets software run on hardware it was not written for, and gives a safe sandbox for testing. The cost is a performance overhead and dependence on the host.
The bit that catches people outPipelining does not make a single instruction faster — each one still takes the same number of stages. It increases throughput: the number of instructions completed per unit time. Confusing latency with throughput misses the point of the technique.
The grown-up words
What it means
What it is called
Note
Few simple fixed-length instructions
RISC
Pipelines cleanly
Many complex variable-length instructions
CISC
More work per instruction
Overlapping instruction stages
pipelining
Increases throughput
Instruction needing a result not yet ready
data hazard
Stalls the pipeline
One instruction on many data items
SIMD
Graphics and arrays
Many instructions on many data items
MIMD
Multi-core processors
Table of ISR addresses
vector table
Used to dispatch interrupts
Software simulating a complete computer
virtual machine
Isolation at a performance cost
Check you have got it
Why does a branch instruction cause a problem in a pipelined processor?
Instructions after the branch have already entered the pipeline. If the branch is taken they are the wrong instructions and must be discarded, flushing the pipeline and wasting those cycles.
Give one advantage and one disadvantage of running software in a virtual machine.
Advantage: it is isolated from the host, so a crash or malware is contained, and software can run on hardware it was not written for. Disadvantage: the emulation layer adds a performance overhead.
Edvia Free Resources · Computer Science 9618 · Topic 15 — free to copy and share
Topic 16
System software (A2)
The operating system's cleverest work is invisible: sharing one processor and one block of memory among programs that all behave as if they own the machine.
Picture itA hotel with fewer rooms than guests, run so well that no guest ever notices. Rooms are swapped, cleaned and reallocated constantly, and every guest believes they have their own permanent room. Virtual memory and process scheduling are that hotel.
Process states
A process is running, ready or blocked. It moves from running to ready when its time slice expires, and to blocked when it waits for I/O. The process control block stores everything needed to resume it: program counter, registers, state and memory limits.
Scheduling algorithms compared
First come first served, shortest job first, shortest remaining time, round robin. High-level scheduling admits jobs to the system; low-level scheduling picks which ready process runs next. Preemptive schedulers can interrupt a running process; non-preemptive ones cannot.
Virtual memory and page replacement
Pages are swapped between RAM and disk. A page fault occurs when a needed page is not in RAM. Replacement algorithms — FIFO, least recently used — decide what to evict. Too many faults and the system is thrashing: swapping more than computing.
Interrupts and the kernel
The kernel is the core, running in a privileged mode with direct hardware access. User programs request kernel services through system calls, which is what stops one program from writing over another's memory or seizing a device.
Assemblers, compilers and interpreters revisited
Two-pass assembly resolves forward references — the first pass builds a symbol table, the second generates code. Compilation stages: lexical analysis produces tokens, syntax analysis builds a parse tree, semantic analysis checks meaning, then code generation and optimisation.
The bit that catches people outA page fault is not an error. It is the normal mechanism by which virtual memory works — the OS fetches the page and continues. A high rate of page faults is the problem, not the existence of one.
The grown-up words
What it means
What it is called
Note
Process currently using the processor
running state
One at a time per core
Process waiting for the processor
ready state
Queued by the scheduler
Process waiting for input or output
blocked state
Cannot use the CPU yet
Structure storing a process's saved state
process control block
Allows resumption
Scheduler that can interrupt a running process
preemptive scheduler
e.g. round robin
Needed page is not in RAM
page fault
OS loads it from disk
Privileged core of the operating system
kernel
Accessed by system calls
Assembly pass building the symbol table
first pass
Resolves forward references
Check you have got it
Why does a two-pass assembler need two passes?
A program can refer to a label defined later in the code. The first pass records every label's address in a symbol table; the second pass can then generate machine code with all addresses known.
What happens to a process when it requests data from a disk?
It moves from running to blocked, freeing the processor for another ready process, and returns to ready once the data arrives.
Edvia Free Resources · Computer Science 9618 · Topic 16 — free to copy and share
Topic 17
Security (A2)
Serious security is layered — because every single measure, taken alone, has a way around it.
Picture itA castle does not rely on the gate. There is a moat, a wall, a portcullis, an inner keep and guards. Each can be defeated; all of them together, rarely. Defence in depth is not paranoia, it is arithmetic.
Encryption protocols in practice
SSL/TLS secures web traffic: the handshake authenticates the server with a certificate, agrees a cipher and exchanges a session key asymmetrically, then switches to fast symmetric encryption for the data.
Digital signatures and hashing
A hash function produces a fixed-length digest from any input, and any change to the input changes the digest. Encrypting the digest with the sender's private key creates a digital signature, proving both origin and integrity. A good hash is one-way and collision-resistant.
Malware and its variants
Virus (attaches to a file), worm (spreads by itself), trojan (disguised as something wanted), spyware, keylogger, ransomware, rootkit, adware. Being precise about the type is what separates a strong answer from a vague one.
Attacks on systems
SQL injection exploits unsanitised input; buffer overflow overwrites memory beyond an array; cross-site scripting injects code into a trusted page; brute force tries every combination; social engineering targets the person. The countermeasures are parameterised queries, bounds checking, input sanitisation, rate limiting and training.
Firewalls, proxies and access control
A firewall filters traffic by rules. A proxy sits between client and server, hiding addresses, caching and filtering. Access control assigns privilege levels, so a compromised ordinary account cannot reach everything.
The bit that catches people outA hash is not encryption. Encryption is reversible with the key; hashing is deliberately one-way. That is precisely why passwords are stored as hashes — even the system operator should not be able to recover them.
The grown-up words
What it means
What it is called
Note
Protocol securing web traffic
SSL/TLS
Handshake then symmetric encryption
Fixed-length one-way summary of data
hash
Any change alters the digest
Encrypted digest proving origin and integrity
digital signature
Uses the private key
Malware that spreads without a host file
worm
A virus attaches to a file
Malware disguised as wanted software
trojan
Relies on the user installing it
Attack overwriting memory past an array
buffer overflow
Prevented by bounds checking
Attack injecting database commands
SQL injection
Prevented by parameterised queries
Server sitting between client and destination
proxy server
Caches, filters, hides addresses
Check you have got it
Why are passwords stored as hashes rather than encrypted?
Hashing is one-way, so even someone who steals the database cannot recover the original passwords. Verification works by hashing the entered password and comparing digests.
How do parameterised queries prevent SQL injection?
User input is passed as a parameter value rather than concatenated into the SQL string, so it can never be interpreted as part of the command.
Edvia Free Resources · Computer Science 9618 · Topic 17 — free to copy and share
Topic 18
Artificial intelligence
AI is a set of techniques for making a program improve at a task from data, rather than from someone writing every rule by hand.
Picture itTeaching someone to recognise a cat. You could write a rule — four legs, whiskers, tail — and immediately meet a cat with three legs. Or you could show them ten thousand pictures labelled cat and not-cat and let them work out the pattern. The second is machine learning, and it is why AI improved once data became abundant.
Categories of AI
Narrow AI performs one specific task. General AI would match human flexibility across tasks and does not exist. Strong AI is the philosophical claim of genuine understanding. Being clear about which you mean prevents most confused arguments about AI.
Machine learning
Supervised learning trains on labelled examples. Unsupervised learning finds structure in unlabelled data, such as clustering. Reinforcement learning learns from rewards and penalties through trial and error. Which one applies is decided by what data you have, not by which is best.
Artificial neural networks
Layers of nodes: input, hidden and output. Each connection carries a weight; each node sums its weighted inputs and applies an activation function. Training adjusts weights via back propagation to reduce error. Deep learning simply means many hidden layers.
Graphs and search algorithms
AI problems are often modelled as graphs. Breadth-first search explores level by level using a queue and finds the shortest path in an unweighted graph. Depth-first uses a stack and goes deep first. Dijkstra's algorithm finds shortest paths on weighted graphs; A* adds a heuristic to guide the search towards the goal faster.
Where it is used, and where it fails
Applications include medical image analysis, translation, autonomous vehicles and fraud detection. Limitations: models inherit bias from training data, need very large datasets, are often hard to interpret, and have no understanding of context outside their training.
The bit that catches people outA neural network cannot explain its reasoning in the way an expert system can. That is precisely why explainability is a live issue in medicine, lending and criminal justice — the output may be accurate and still be unusable if nobody can justify it.
The grown-up words
What it means
What it is called
Note
AI performing one specific task
narrow AI
What exists today
Training on labelled examples
supervised learning
Classification, regression
Finding structure in unlabelled data
unsupervised learning
e.g. clustering
Learning from rewards and penalties
reinforcement learning
Trial and error
Layers of weighted connected nodes
artificial neural network
Input, hidden, output
Adjusting weights to reduce error
back propagation
How networks train
Search exploring level by level
breadth-first search
Uses a queue
Shortest path on a weighted graph
Dijkstra's algorithm
A* adds a heuristic
Check you have got it
Which search would you use to find the fewest moves in an unweighted puzzle, and why?
Breadth-first search. It explores all nodes at one depth before going deeper, so the first time it reaches the goal it has used the fewest moves.
Why can a machine learning model be biased even when the algorithm is neutral?
The model learns patterns from its training data. If that data reflects historic bias, the model reproduces it — the algorithm has no way to know a pattern is unjust.
Edvia Free Resources · Computer Science 9618 · Topic 18 — free to copy and share
Topic 19
Computational thinking and problem-solving
Some problems have a natural structure of the same shape repeating inside itself, and recognising that changes how you solve them.
Picture itRussian dolls. To open all of them, you open the outer one and then face exactly the same problem with a smaller doll — until you reach one that does not open. That final doll is the base case, and without it you never stop.
Recursion
A recursive routine calls itself on a smaller version of the problem, and has a base case that stops it. Each call is placed on the call stack with its own local variables and return address; too deep a recursion causes stack overflow. Recursion is elegant for trees and divide-and-conquer, but it costs stack space.
Recursion versus iteration
Anything recursive can be written iteratively, and vice versa. Recursion is clearer for naturally recursive structures — tree traversal, quicksort, the Towers of Hanoi. Iteration is usually faster and uses constant stack space. The choice is readability against resource use.
Sorting and searching algorithms compared
Bubble and insertion sort are O(n²). Quicksort partitions around a pivot and recurses, averaging O(n log n). Merge sort divides, sorts and merges, guaranteeing O(n log n) but needing extra memory. Binary search is O(log n) on sorted data.
Big O notation
Big O describes how running time grows with input size, ignoring constants. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2ⁿ) exponential. It is about growth, not stopwatch time — an O(n²) algorithm can beat an O(n log n) one on small inputs.
Abstraction and decomposition at scale
Large systems are made tractable by hiding detail behind interfaces and splitting work into independent modules. This is the same idea as in the AS course, applied where the alternative is genuinely unmanageable.
The bit that catches people outA recursive routine without a reachable base case does not loop forever quietly — it consumes stack space with every call until the program crashes with a stack overflow. That is a different failure from an infinite loop, and the exam distinguishes them.
The grown-up words
What it means
What it is called
Note
Routine that calls itself
recursive routine
Needs a base case
The condition that stops the recursion
base case
Without it, stack overflow
Memory holding return addresses and locals
call stack
Grows with each call
Sort partitioning around a pivot
quicksort
Average O(n log n)
Sort dividing, sorting and merging
merge sort
Guaranteed O(n log n)
Notation for growth of running time
Big O notation
Ignores constants
Time growing with the square of input size
O(n squared)
Bubble, insertion sort
Time growing logarithmically
O(log n)
Binary search
Check you have got it
Why does merge sort guarantee O(n log n) while quicksort does not?
Merge sort always divides the list exactly in half. Quicksort's split depends on the pivot; a consistently poor pivot gives very uneven partitions and degrades to O(n²).
Give one advantage of iteration over recursion.
Iteration uses constant stack space and avoids the overhead of repeated function calls, so it is generally faster and cannot cause a stack overflow.
Edvia Free Resources · Computer Science 9618 · Topic 19 — free to copy and share
Topic 20
Further programming
Object-oriented programming organises a program around the things it models, keeping each thing's data and behaviour together.
Picture itA car showroom. Rather than a giant list of every car's colour and every car's engine size in separate tables, each car object carries its own details and knows how to start, stop and report itself. Adding an electric car means writing what is different about it, not rewriting the showroom.
Classes and objects
A class is a template; an object is an instance of it. Attributes hold state and methods define behaviour. A constructor runs when an object is created, setting its initial state.
Encapsulation
Attributes are made private and accessed through public get and set methods. This means the class controls how its data changes — a setter can validate — and the internal representation can change without breaking any code that uses the class.
Inheritance
A subclass inherits attributes and methods from its superclass and adds or overrides what it needs. This avoids duplicated code and expresses genuine 'is-a' relationships. Overuse creates fragile deep hierarchies, so it is a tool with a cost.
Polymorphism
The same method call behaves differently depending on the object's actual class. A list of Shape objects can each be told to draw themselves, and each does its own thing — so new shapes can be added without touching the drawing loop.
Files, exceptions and libraries
Reading and writing text and binary files, serialisation of objects, and structured exception handling with try/catch so a program handles a missing file or bad input rather than crashing. Library modules let you reuse tested code instead of rewriting it.
The bit that catches people outInheritance and encapsulation pull in opposite directions, and knowing that is a genuinely advanced point. A subclass reaching into its parent's internals creates exactly the coupling encapsulation was meant to prevent — which is why protected access should be used sparingly.
The grown-up words
What it means
What it is called
Note
Template defining attributes and methods
class
Objects are its instances
A specific instance of a class
object
Has its own attribute values
Method run when an object is created
constructor
Sets initial state
Hiding attributes behind get and set methods
encapsulation
Class controls its data
Subclass acquiring a superclass's members
inheritance
Expresses an is-a relation
Same call behaving differently per class
polymorphism
Enables generic code
Subclass replacing an inherited method
overriding
Same name, new behaviour
Handling errors without crashing
exception handling
try / catch
Check you have got it
Why are attributes usually made private with public get and set methods?
So the class controls how its data is read and changed — a setter can validate input — and the internal representation can be altered later without breaking code that uses the class.
How does polymorphism let you add a new shape to a drawing program without changing the drawing loop?
The loop calls the same method on every object. Each subclass provides its own version, so a new subclass supplying that method works immediately with the existing loop.
Edvia Free Resources · Computer Science 9618 · Topic 20 — free to copy and share
Like how this is taught?
Every handout starts with the idea in plain English and only then the formal version. That is how every class at Edvia College works — for two full years of Cambridge A Levels.