Computer Science Cheat Sheets — GCSE & A Level

🔢

Binary & Hexadecimal

All specs

Conversions

Binary→Denary

Multiply each bit by place value (128,64,32,16,8,4,2,1) and sum

Denary→Binary

Repeatedly subtract largest possible power of 2, mark 1/0

Binary→Hex

Group into nibbles of 4, convert each (1010=A, 1111=F etc.)

Hex→Denary

Multiply each digit by 16ⁿ position and sum

Binary addition

Add column by column right to left; 1+1=10 (write 0, carry 1)

Two's Complement (Signed Numbers)

Positive numbers

Same as unsigned binary — MSB = 0

-ve from +ve

Invert all bits, then add 1

MSB value

In 8-bit: MSB represents −128 (not +128)

Range (8-bit)

−128 to +127

Overflow

Result too large for available bits — wraps around incorrectly

Character Encoding

ASCII

7-bit, 128 characters — English letters, digits, symbols

Extended ASCII

8-bit, 256 characters — adds some accented chars

Unicode (UTF-8)

Variable width — covers every language and emoji worldwide

UTF-16

16-bit minimum — used internally by Java, Windows

Code point

Unicode number for a character e.g. U+0041 = 'A'

File Size Formulas

Images

width × height × colour depth (bits)

Audio

sample rate × bit depth × duration × channels (bits)

Divide by 8

bits → bytes

Divide by 1000 or 1024

bytes → KB → MB → GB (1024 for binary prefixes)

Number of Values

n bits →

2ⁿ possible values

8 bits (1 byte)

256 values (0–255 unsigned)

24-bit colour

16.7 million colours

Example: 4 bits

2⁴ = 16 values

🌐

Computer Networks

All specs

Key Hardware

Router

Routes packets between networks using IP addresses

Switch

Sends frames to correct device in LAN using MAC addresses

Hub

Broadcasts to ALL devices — obsolete, replaced by switch

NIC

Network Interface Card — connects device to network, has MAC address

WAP

Wireless Access Point — provides Wi-Fi connection to wired network

Modem

Modulates/demodulates signal between digital and analogue (ISP link)

TCP/IP Layers

Application (4)

HTTP, FTP, SMTP, DNS — user-facing protocols

Transport (3)

TCP (reliable, ordered) / UDP (fast, no guarantee) — ports & segments

Internet (2)

IP — logical addressing, routing packets across networks

Link (1)

Ethernet, Wi-Fi — physical transmission on local network, MAC addresses

Key Protocols & Ports

HTTP / HTTPS

Port 80 / 443 — web page transfer

FTP

Port 20/21 — file transfer

SMTP

Port 25 — sending email

IMAP / POP3

Port 143 / 110 — receiving email

DNS

Port 53 — domain name → IP address lookup

SSH

Port 22 — secure encrypted remote login

Network Topologies

Star

All devices → central switch. Best performance. Switch = single point of failure

Bus

All devices → shared backbone. Cheap to set up. Backbone failure = total failure

Mesh

Every node connected to many others. Highly resilient. Expensive. Used in WANs

IP & Addressing

IPv4

32-bit (4 octets): 192.168.1.1 — approx. 4.3 billion unique addresses

IPv6

128-bit hexadecimal — virtually unlimited addresses, replacing IPv4

MAC address

48-bit hardware identifier — used within LAN (Layer 1/2 only)

DHCP

Automatically assigns IP addresses to devices joining a network

DNS

Translates human-readable domain name to IP address

TCP vs UDP

TCP

Connection-oriented, reliable, ordered — web, email, file transfer

UDP

Connectionless, fast, no guarantee — streaming, VoIP, DNS, gaming

TCP handshake

SYN → SYN-ACK → ACK (3-way handshake before data)

🛡️

Cybersecurity

All specs

CIA Triad

Confidentiality

Only authorised users can access data — encryption, access controls, 2FA

Integrity

Data is accurate and unaltered — hashing, digital signatures, checksums

Availability

Systems accessible when needed — backups, redundancy, DDoS mitigation

Attack Types

Phishing

Fake emails/sites to steal credentials — targeted version = spear phishing

Brute force

Tries every possible password combination systematically

Dictionary attack

Tries common words/passwords from a pre-compiled list — faster than brute force

DDoS

Floods server with traffic from many compromised machines (botnet)

Malware

Virus, worm, ransomware, spyware, Trojan, keylogger

SQL injection

Malicious SQL inserted into input fields — use parameterised queries to prevent

Man-in-middle

Secretly intercepts and possibly alters communications between two parties

Zero-day

Exploits an unknown or unpatched vulnerability before a fix exists

Social Engineering

Phishing

Mass fake email impersonating trusted organisation

Spear phishing

Targeted phishing using personal details about the victim

Pretexting

Fabricated scenario to gain trust (e.g. posing as IT support)

Tailgating

Following an authorised person through a secure door

Baiting

Leaving infected USB drive for victim to find and plug in

Defences

Firewall

Filters network traffic by rules (IP address, port, protocol)

Antivirus

Detects/removes malware using signatures and heuristic analysis

Encryption

Scrambles data — needs correct key to decrypt

2FA / MFA

Two or more independent verification steps required

Patching

Apply software updates promptly to fix known vulnerabilities

Penetration testing

Authorised simulated attack to discover vulnerabilities before attackers do

Least privilege

Users only have permissions they actually need — limits damage from breaches

Encryption

Symmetric

Same key encrypts and decrypts — fast, but key distribution is a problem

Asymmetric

Public key encrypts, private key decrypts — used in TLS/HTTPS/email signing

Hashing

One-way function — same input always gives same hash — used for passwords, integrity

Digital signature

Sender hashes message and encrypts hash with private key — proves authenticity

TLS handshake

Asymmetric crypto exchanges a symmetric session key; then symmetric used for speed

⚙️

Algorithms & Complexity

A LevelGCSE

Big O Complexity

O(1)

Constant — array index access, hash table lookup

O(log n)

Binary search, balanced BST operations

O(n)

Linear search, traversing a list once

O(n log n)

Merge sort, quicksort average case

O(n²)

Bubble, insertion, selection sort — nested loops

O(2ⁿ)

Recursive Fibonacci, brute-force subset problems

Sorting Algorithms

Bubble

Compare adjacent pairs, swap if out of order. Repeat passes. O(n²) worst, O(n) best

Merge

Recursively split in half, merge sorted halves. O(n log n) always. Stable. Needs O(n) space

Insertion

Build sorted portion left to right; insert each element in correct position. O(n²) worst

Quicksort

Choose pivot, partition around it, recurse. O(n log n) avg, O(n²) worst. In-place

Selection

Find minimum in unsorted portion, swap to front. O(n²) always

Search

Linear search

O(n) — check each item in turn — works on any list, unsorted or sorted

Binary search

O(log n) — halves search space each step — sorted list ONLY

Graph Algorithms (A Level)

Dijkstra's

Shortest path from one source — weighted graph, no negative edges

Dijkstra's + heuristic estimate — more efficient for pathfinding

BFS

Breadth-first search — finds shortest path (unweighted) — uses queue

DFS

Depth-first search — explores as deep as possible — uses stack or recursion

Recursion

Base case

Condition that stops recursion — MUST exist or infinite recursion occurs

Recursive case

Function calls itself with a smaller/simpler version of the problem

Call stack

Each recursive call adds a stack frame — risk of stack overflow if too deep

vs Iteration

Recursion: elegant for trees, divide-and-conquer. Iteration: usually more memory efficient

🗃️

Data Structures

A Level

Structures Comparison

Array

O(1) indexed access, fixed size — fast iteration, cache-friendly

Linked list

O(n) access, dynamic size — O(1) insert/delete at known node

Stack (LIFO)

Push/Pop from top — call stack, undo history, bracket parsing, DFS

Queue (FIFO)

Enqueue/Dequeue — scheduling, BFS, print queue, buffers

Hash table

O(1) avg access — key→hash→index, collisions handled by chaining/probing

BST

O(log n) avg search/insert — left < root < right — degrades to O(n) if unbalanced

Tree Terms

Root

Top node — has no parent

Leaf

Node with no children

Height

Length of longest path from root to a leaf

Balanced BST

Left and right subtrees have similar height — maintains O(log n)

Degenerate tree

Every node has one child — behaves like a linked list — O(n) search

Tree Traversals

In-order (L→Root→R)

Visits BST nodes in ascending sorted order

Pre-order (Root→L→R)

Useful for copying or serialising tree structure

Post-order (L→R→Root)

Useful for deleting a tree or evaluating expression trees / RPN

Graphs

Directed (digraph)

Edges have direction — one-way relationships (e.g. web links)

Undirected

Edges go both ways — two-way relationships (e.g. roads)

Weighted

Edges carry a cost or distance value

Adjacency matrix

2D array — O(1) lookup, O(V²) space — good for dense graphs

Adjacency list

Array of neighbour lists — O(V+E) space — good for sparse graphs

🗄️

Databases & SQL

A LevelGCSE

SQL Clauses

SELECT cols

Choose columns (* = all columns)

FROM table

Specify the source table

WHERE cond

Filter rows — use AND, OR, NOT, LIKE, BETWEEN, IN

JOIN t2 ON col

Combine tables on matching column (INNER, LEFT, RIGHT)

GROUP BY col

Group rows for aggregate functions

HAVING cond

Filter groups (like WHERE but for aggregates)

ORDER BY col

Sort result ASC (default) or DESC

LIMIT n

Return only the first n rows

SQL Aggregates & DML

COUNT(*) / COUNT(col)

Count rows / count non-null values

SUM(col) / AVG(col)

Total / average of numeric column

MAX(col) / MIN(col)

Highest / lowest value

INSERT INTO t (cols) VALUES (vals)

Add a new row

UPDATE t SET col=val WHERE cond

Modify existing rows — always include WHERE

DELETE FROM t WHERE cond

Remove rows — always include WHERE or ALL rows deleted

Key Concepts

Primary key

Uniquely identifies each row — no nulls, no duplicates

Foreign key

References primary key of another table — enforces referential integrity

Referential integrity

FK must always reference an existing PK — no orphaned records

1NF

Atomic values, no repeating groups, has a primary key

2NF

1NF + no partial dependencies (non-key attribute depends on WHOLE composite PK)

3NF

2NF + no transitive dependencies (non-key attribute depends only on PK, not other non-key)

ACID Properties

Atomicity

Transaction is all-or-nothing — if any step fails, all changes roll back

Consistency

Transaction brings DB from one valid state to another — constraints always satisfied

Isolation

Concurrent transactions don't interfere — each executes as if alone

Durability

Committed transactions survive crashes — written to persistent storage

💻

Programming Fundamentals

All specs

Three Constructs

Sequence

Instructions execute in the written order, one after another

Selection

IF / ELIF / ELSE — branch based on a condition being true or false

Iteration

FOR (count-controlled) or WHILE (condition-controlled) — repeat a block

Data Types

Integer

Whole numbers: 5, -3, 0

Float / Real

Decimal numbers: 3.14, -0.5

String

Text enclosed in quotes: "hello", "42"

Boolean

True or False only

Char

Single character: 'A'

Casting

int("5")→5 str(5)→"5" float("3.14")→3.14

Subroutines

Procedure

Executes a named block of code — returns no value

Function

Executes a block of code — RETURNS a value to the caller

Parameter

Variable declared in the subroutine definition

Argument

Actual value supplied when the subroutine is called

By value

A copy is passed — changes inside do NOT affect the original

By reference

Memory address passed — changes inside DO affect the original

Validation Types

Range check

Value falls within min–max bounds (e.g. age 0–120)

Presence check

Field is not empty / not null

Type check

Input is the correct data type (e.g. integer, not text)

Length check

Input has the correct number of characters

Format check

Input matches a required pattern (e.g. date DD/MM/YYYY, postcode)

Common String Operations

len(s)

Number of characters in string

s.upper() / s.lower()

Convert to UPPER or lower case

s[i]

Character at index i (0-based)

s[a:b]

Slice — characters from index a up to (not including) b

s + t

Concatenate two strings

s.split(sep)

Split string into list on separator

🏛️

Object-Oriented Programming

A Level

OOP Pillars

Encapsulation

Bundle data and methods together; hide internal state using private access

Inheritance

Child class inherits attributes and methods from parent — promotes code reuse

Polymorphism

Same method name, different behaviour depending on the object's class (overriding)

Abstraction

Hide complex implementation — show only what is necessary via abstract classes/interfaces

Key Terms

Class

Blueprint/template that defines attributes and methods for its objects

Object

An instance of a class — created by calling the constructor

Constructor

Special method that initialises a new object (__init__ in Python)

Method

A function that belongs to a class and operates on the object's data

Attribute

A data variable that belongs to an object (instance variable)

this / self

Reference to the current object instance within its own methods

Access Modifiers

public

Accessible from anywhere — any code can read or write this member

private

Only accessible within the same class — enforces encapsulation

protected

Accessible within the class and any subclasses

Getter / Setter

Controlled public access to private attributes — validates before setting

Inheritance & Interfaces

Overriding

Subclass provides its own version of an inherited method (runtime polymorphism)

Overloading

Same method name, different parameter lists in the same class (compile-time)

Abstract class

Cannot be instantiated — defines abstract methods subclasses MUST implement

Interface

Pure contract — only method signatures, no implementation — a class can implement many

super()

Call the parent class's method or constructor from within a subclass

🖥️

CPU & Computer Architecture

All specs

Von Neumann Model

Stored program concept

Program instructions and data held together in main memory

CPU

Central Processing Unit — carries out program instructions

RAM

Main memory — holds current program and data — volatile (lost on power off)

ALU

Arithmetic Logic Unit — performs arithmetic and logical comparisons

Control Unit — fetches, decodes, and directs instruction execution

Buses

Address bus (location), Data bus (content), Control bus (read/write signals)

Key Registers

Program Counter — holds address of the NEXT instruction to be fetched

MAR

Memory Address Register — holds address currently being read from or written to

MDR

Memory Data Register — holds data just fetched from or about to be written to memory

CIR / IR

Current Instruction Register — holds the instruction currently being decoded

Accumulator

Stores the result of the most recent ALU operation

SR / Flags

Status Register — condition flags: zero, negative, carry, overflow

Fetch-Decode-Execute Cycle

1. Fetch

MAR ← PC; MDR ← Memory[MAR]; CIR ← MDR; PC ← PC + 1

2. Decode

CU interprets the opcode in the CIR to determine the operation

3. Execute

ALU performs the calculation, or data is moved between registers/memory

CPU Performance Factors

Clock speed

More cycles per second = more instructions per second (GHz)

Number of cores

Multiple cores execute different instruction streams in parallel

Cache size

Larger/faster cache reduces time spent waiting for RAM (L1→L2→L3 hierarchy)

Pipelining

Overlaps fetch-decode-execute stages of different instructions simultaneously

Word size

Bits processed at once — wider word processes more data per cycle

Memory Hierarchy

Registers

Fastest and smallest — inside the CPU — sub-nanosecond access

L1/L2/L3 Cache

Very fast SRAM — stores recently used instructions and data

RAM (main memory)

Volatile — microsecond access — all running programs reside here

SSD / HDD

Non-volatile persistent storage — millisecond access — far slower than RAM

Virtual memory

Disk space used as RAM extension — causes thrashing if overused

⚡

Boolean Logic & Logic Gates

All specs

Logic Gates

AND

Output 1 only when ALL inputs are 1

Output 1 when AT LEAST ONE input is 1

NOT

Inverts a single input: 0→1, 1→0 (also called an inverter)

NAND

NOT AND — output 0 only when all inputs are 1 (universal gate — can build any circuit)

NOR

NOT OR — output 1 only when all inputs are 0 (universal gate)

XOR

Exclusive OR — output 1 only when inputs are DIFFERENT

Truth Table Summary

AND: 0,0 / 0,1 / 1,0 / 1,1

0 / 0 / 0 / 1

OR: 0,0 / 0,1 / 1,0 / 1,1

0 / 1 / 1 / 1

XOR: 0,0 / 0,1 / 1,0 / 1,1

0 / 1 / 1 / 0

NAND: opposite of AND

1 / 1 / 1 / 0

NOR: opposite of OR

1 / 0 / 0 / 0

De Morgan's Laws

Law 1

NOT(A OR B) ≡ NOT A AND NOT B

Law 2

NOT(A AND B) ≡ NOT A OR NOT B

Memory trick

Break the bar, flip the operator (OR↔AND)

Use case

Convert NOR/NAND expressions; simplify and minimise logic circuits

Boolean Identities

A AND 1 = A

Identity — AND with TRUE returns the other input

A OR 0 = A

Identity — OR with FALSE returns the other input

A AND 0 = 0

Annihilation — AND with FALSE always gives FALSE

A OR 1 = 1

Annihilation — OR with TRUE always gives TRUE

A AND NOT A = 0

Complement — always false (contradiction)

A OR NOT A = 1

Complement — always true (tautology)

NOT(NOT A) = A

Double negation law

Half Adder & Full Adder

Half adder inputs

Two 1-bit inputs: A and B

Half adder outputs

Sum = A XOR B | Carry = A AND B

1+1 result

Sum = 0, Carry = 1 (represents binary 10)

Full adder

Adds A + B + carry-in → produces Sum and carry-out

Ripple carry adder

Chain of full adders for multi-bit binary addition

📦

Compression & Encoding

All specs

Lossy vs Lossless

Lossless

Original data perfectly reconstructed — no information lost

Lossy

Some data permanently discarded — smaller file, cannot fully recover original

Use lossless for

Text, source code, databases, spreadsheets, medical images — accuracy essential

Use lossy for

Photos (JPEG), music (MP3), video (MP4/H.264) — small quality loss acceptable

Trade-off

Higher compression ratio = more quality lost (lossy only)

Run-Length Encoding (RLE)

Idea

Replace consecutive runs of the same value with a count and the value

Example

AAAABBBCC → 4A 3B 2C (saves space when many repeats)

Best for

Images with large areas of solid colour — simple graphics, fax documents

Worst for

Photographs or text — very few consecutive identical values

Type

Lossless

Huffman Coding

Idea

Assign shorter binary codes to more frequent characters

Build tree

Create leaf for each symbol weighted by frequency; repeatedly merge two lowest-frequency nodes

Prefix-free

No code is a prefix of another — allows unambiguous decoding

Result

Frequent characters use fewer bits; rare characters use more bits

Type

Lossless — used in ZIP, PNG, GZIP, DEFLATE

Requires

Frequency table (dictionary) must be sent alongside compressed data

Why Compress?

Storage

Smaller files use less disk space and cloud storage

Transmission

Faster to transfer — less bandwidth required

Streaming

Video and audio delivered in real-time at lower bitrate

Cost

Reduced storage and bandwidth costs for services and users

🖧

Operating Systems

All specs

OS Roles

Process management

Creates, schedules, and terminates processes — manages multitasking

Memory management

Allocates RAM to processes, manages paging and virtual memory

File management

Organises files in a file system — handles read, write, permissions

Device management

Communicates with hardware peripherals via device drivers

User interface

CLI (command line) or GUI — allows user interaction with the system

Security

User authentication, access control, file permissions

CPU Scheduling Algorithms

FCFS

First Come First Served — simple, non-preemptive — convoy effect for long jobs

Round Robin

Each process gets a time slice (quantum); rotates — fair, good response time

SJF

Shortest Job First — minimises average wait time — needs burst time estimate

Priority

Higher-priority processes run first — risk of starvation for low-priority processes

Preemptive

OS can interrupt a running process mid-execution to run higher-priority task

Non-preemptive

Process runs until it completes or blocks — simpler but less responsive

Memory Management

Virtual memory

Uses disk as RAM extension — pages swapped in/out as needed

Paging

Divides memory into fixed-size pages — eliminates external fragmentation

Thrashing

Constant page swapping — performance collapses — symptom of too little RAM

Memory protection

Each process can only access its own allocated memory region

Interrupts

Hardware interrupt

Peripheral signals CPU — keypress, network packet received, timer fired

Software interrupt

Program makes a system call or an exception occurs (e.g. divide by zero)

ISR

Interrupt Service Routine — code that handles the specific interrupt

Process

CPU saves state (registers/PC) → executes ISR → restores state → continues

Types of OS

Batch

Jobs queued and processed without user interaction — e.g. payroll, data processing

Multi-user

Multiple users share resources simultaneously — e.g. Linux server, mainframe

Real-time (RTOS)

Guaranteed response within strict time bounds — e.g. aircraft, pacemaker, ABS

Distributed

Processing spread across multiple networked machines — appears as one system

Embedded

Minimal OS in dedicated hardware — e.g. microwave, washing machine, car ECU