Cambridge IAL Computer Science cheat sheet

Decomposition: split a problem into sub-problems that can be solved and tested independently; each sub-problem should have a defined input, output and interface.

Abstraction: remove detail irrelevant to the current purpose, keeping only the properties needed; a model is valid only for the questions it was built to answer.

Algorithmic thinking: an algorithm is a finite, ordered, unambiguous sequence of steps that terminates; each step must be executable without further interpretation.

Linear search is O(n) and works on unsorted data; binary search is O(log n) but requires the data to be sorted before searching.

Bubble sort worst case O(n^2), best case O(n) with a swap flag; insertion sort O(n^2) worst, O(n) on nearly sorted data; merge sort O(n log n) in all cases but needs O(n) extra space.

Recursion needs a base case that terminates and a recursive case that moves toward it; each call adds a stack frame, so deep recursion risks stack overflow.

Big-O describes the growth of the dominant term as input size grows; constants and lower-order terms are discarded, so 3n^2 + 5n + 7 is O(n^2).

A finite state machine is defined by states, an input alphabet, a transition function, a start state and accepting states; it has no memory beyond its current state.

Procedural programming organises code as named subroutines operating on shared or passed data; state changes are explicit and sequenced by the programmer.

Object-oriented programming bundles attributes (state) and methods (behaviour) into objects; a class is the template, an object is an instance created at run time.

Encapsulation hides internal state behind public methods; inheritance lets a subclass reuse and extend a superclass; polymorphism lets one method name behave differently per class.

Declarative programming states what result is required rather than how to compute it; SQL queries and logic (Prolog-style) rules are declarative examples.

Functional programming treats functions as first-class values and avoids mutable state; pure functions return the same output for the same input and cause no side effects.

A compiler translates the whole source program to machine code before execution, reporting all syntax errors at once; an interpreter translates and runs line by line, stopping at the first error.

Assemblers translate mnemonics to machine code; a linker combines compiled object modules and library routines into one executable, resolving external references.

Pass by value copies the argument, so the caller's variable is unchanged; pass by reference passes the address, so changes inside the subroutine affect the caller.

The OSI seven layers, bottom to top: physical, data link, network, transport, session, presentation, application.

TCP is connection-oriented: it handshakes, numbers segments, acknowledges receipt, retransmits lost segments and reorders them; UDP is connectionless with no delivery guarantee and lower overhead.

IPv4 addresses are 32 bits; IPv6 addresses are 128 bits written as eight hexadecimal groups, giving a vastly larger address space.

A MAC address is 48 bits and identifies a network interface within a LAN; an IP address identifies a host for routing between networks.

Circuit switching reserves a dedicated path for the whole session; packet switching splits data into packets routed independently, giving better link utilisation.

A hub broadcasts to all ports in one collision domain; a switch forwards frames by MAC address per port; a router forwards packets between networks by IP address.

Parity detects an odd number of bit errors only; a checksum sums data blocks and compares totals; ARQ uses acknowledgements and timeouts to request retransmission.

Symmetric encryption uses one shared key and is fast; asymmetric encryption uses a public/private key pair and is slower, so it is typically used to exchange a symmetric session key.

The fetch-decode-execute cycle: copy the address in the program counter to MAR, fetch the instruction into MDR and CIR, increment the PC, decode, then execute.

The registers in the von Neumann model are PC (next address), MAR (address being accessed), MDR (data in transit), CIR (current instruction) and the accumulator.

The ALU performs arithmetic and logical operations; the control unit decodes instructions and issues control signals; status flags record zero, carry, overflow and sign.

The stored-program concept: instructions and data share the same memory and are both held as binary, so a program can be loaded and modified like data.

A von Neumann bottleneck arises because instructions and data share one bus, so the CPU may wait on memory; cache memory reduces this by holding recently used data close to the CPU.

RISC uses a small fixed-length instruction set with many registers and pipelining; CISC uses variable-length, more complex instructions often decoded into micro-operations.

Address bus width determines the number of addressable memory locations (n lines gives 2^n locations); data bus width sets how many bits transfer per cycle.

An interrupt is a signal that suspends the current process, saves its state, runs an interrupt service routine, then restores state; polling checks devices repeatedly instead.

Two's complement: invert all bits of the positive value and add 1; in an n-bit number the leftmost bit has place value -2^(n-1), giving the range -2^(n-1) to 2^(n-1)-1.

Signed magnitude uses the leftmost bit as a sign bit, producing two representations of zero (+0 and -0), which two's complement avoids.

Binary shift left by n bits multiplies by 2^n; logical shift right divides by 2^n, discarding bits; arithmetic shift right preserves the sign bit.

A stack is last-in-first-out with push and pop at one end; a queue is first-in-first-out with enqueue at the rear and dequeue at the front.

A linked list stores each item in a node with a pointer to the next node; insertion and deletion are O(1) once the position is known, but access is O(n) because there is no indexing.

A binary search tree keeps left subtrees smaller and right subtrees larger than the root, giving O(log n) search when balanced and O(n) when degenerate.

A hash table maps a key to an index via a hash function; collisions are resolved by chaining (lists per bucket) or open addressing (probing the next free slot).

A vector graphic stores objects as geometric primitives with attributes and scales without loss; a bitmap stores a pixel grid, so enlarging reveals individual pixels.

A linear search checks each item in turn and can be used on any list; a binary search repeatedly halves a sorted list and needs a midpoint calculation each pass.

Time complexity of an algorithm is measured by counting the dominant operations as a function of input size, not by timing on one machine.

A truth table with n Boolean inputs has 2^n rows; a logic expression can be simplified using Boolean identities such as De Morgan's laws and absorption.

A graph consists of vertices and edges; an adjacency matrix uses O(V^2) space, an adjacency list uses O(V+E) and suits sparse graphs better.

Dijkstra's algorithm finds shortest paths from one source on non-negative weighted graphs; A* adds a heuristic estimate to guide the search toward the goal.

A dry run traces variable values step by step through an algorithm to verify logic and locate errors before execution.

A heuristic is a rule that gives a good-enough solution quickly without guaranteeing optimality, used when an exact algorithm would be too slow.

A local variable exists only within the subroutine that declares it; a global variable is accessible throughout the program and raises the risk of unintended modification.

A parameter is the named placeholder in a subroutine definition; an argument is the actual value supplied at the call.

A function returns a value; a procedure performs an action and returns nothing; both are subroutines that support reuse and modular testing.

Iteration uses a loop with an explicit termination condition; recursion expresses repetition by a function calling itself, and any recursive solution can be rewritten iteratively.

A syntax error breaks the grammar rules and is caught at compile time; a logic error produces wrong output with no error message and is found only by testing.

A record (struct) groups fields of possibly different types under one name; an array holds multiple elements of the same type under one identifier.

An IDE typically provides an editor, compiler or interpreter, debugger with breakpoints, and error diagnostics in one environment.

A library is a collection of pre-written routines linked into a program; an API defines how those routines are called without exposing their implementation.

A protocol is an agreed set of rules covering data format, timing, sequencing and error control so two devices can exchange data.

Bandwidth is the range of frequencies a channel can carry or its maximum data rate; bit rate is the number of bits transmitted per second.

Latency is the delay between sending and receiving; a baud rate counts signal changes per second and equals the bit rate only when each change carries one bit.

A LAN covers a small area such as one building; a WAN spans large distances and typically links LANs through leased lines or public networks.

A star topology connects every device to a central switch or hub; a mesh connects nodes to multiple others, giving redundancy at higher cabling cost.

The TCP/IP four-layer model: application, transport, internet, network access; it maps onto the seven-layer OSI model used for teaching.

A firewall filters incoming and outgoing traffic by rules on address, port and protocol; a proxy server forwards requests on behalf of clients.

A digital signature encrypts a hash of the message with the sender's private key, so the receiver can verify integrity and origin using the public key.

A GPU has many simple cores optimised for parallel arithmetic, while a CPU has fewer complex cores optimised for sequential, branch-heavy code.

Clock speed is cycles per second; a higher clock alone does not guarantee faster execution because instructions per cycle and memory access also matter.

RAM is volatile and holds programs and data in current use; ROM is non-volatile and typically stores firmware such as the boot loader.

Cache levels L1, L2 and L3 trade size against speed; L1 is smallest and fastest and closest to the core.

SSD storage uses flash memory with no moving parts, giving faster random access and greater shock resistance than a magnetic hard disk.

Pipelining overlaps instruction stages to raise throughput, but hazards (data, control, structural) can stall the pipeline and reduce the gain.

A bus carries addresses, data and control signals; the control bus carries read/write and interrupt signals rather than data values.

Virtual memory maps logical addresses to physical addresses via a page table, letting programs exceed physical RAM by paging inactive pages to disk.

Hexadecimal digits 0-9 and A-F represent 4 bits each, so one byte is exactly two hex digits; conversion to binary is done digit by digit.

To convert a positive denary integer to binary, divide repeatedly by 2 and read the remainders bottom to top.

Floating point stores a sign, a mantissa and an exponent; increasing mantissa bits raises precision, increasing exponent bits raises range.

Underflow occurs when a value is too small to represent; overflow occurs when it exceeds the largest representable magnitude.

ASCII uses 7 bits per character (128 codes); Unicode uses variable encoding such as UTF-8 and covers many more characters and scripts.

Lossless compression (for example run-length encoding or Huffman coding) allows exact reconstruction; lossy compression discards detail permanently.

A one-dimensional array stores elements in contiguous memory and is accessed by index in O(1); a two-dimensional array is indexed by row and column.

A tree is a connected acyclic graph with one root; a binary tree limits each node to at most two children, and a full binary tree fills every level.

A test plan should include normal, boundary and erroneous data; boundary values sit at the edges of valid ranges, such as the minimum and maximum permitted inputs.

A white-box test examines internal logic and code paths; a black-box test checks outputs against inputs without reference to the implementation.

A trace table records each variable's value after every step, which exposes off-by-one errors and incorrect loop conditions.

A linear search on n items performs at most n comparisons; a binary search performs at most ceil(log2(n+1)) comparisons on a sorted list.

Merge sort repeatedly halves the list, sorts each half and merges them; quicksort partitions around a pivot and degrades to O(n^2) on already sorted data with a poor pivot choice.

A program specification defines required inputs, outputs and constraints; validation checks input is reasonable (range, type, length) while verification checks it matches the original source.

Abstraction in a model means keeping only the variables that affect the answer; a simulation that omits a relevant variable gives unreliable predictions.

Selection uses IF, IF-ELSE or CASE; iteration uses FOR (count-controlled) or WHILE/REPEAT (condition-controlled) loops.

A WHILE loop tests its condition before the body and may run zero times; a REPEAT-UNTIL loop tests after the body and always runs at least once.

A CASE (switch) statement selects one branch by matching a value against constants, which is clearer than a long IF-ELSE chain.

A stack frame holds a subroutine's parameters, local variables and return address; it is pushed on call and popped on return.

A recursive function needs a base case and a recursive case that reduces the problem size, otherwise it recurses until the stack overflows.

A class defines attributes and methods; instantiation creates an object; a constructor initialises the object's attributes when it is created.

Method overriding replaces a superclass method with a subclass version of the same signature; overloading defines several methods with the same name but different parameters.

An abstract data type specifies operations and behaviour without fixing the implementation; a stack can be implemented with an array or a linked list.

A subnet mask separates the network and host portions of an IPv4 address; a /24 mask leaves 8 host bits, giving 254 usable host addresses.

DHCP automatically assigns IP addresses, subnet masks, gateway and DNS server addresses to hosts joining a network.

DNS resolves a human-readable domain name to an IP address by querying a hierarchy of name servers.

NAT translates private internal addresses to a public address, letting many hosts share one routable IPv4 address.

HTTP is stateless and requests resources; HTTPS adds TLS encryption; FTP transfers files; SMTP sends mail while POP3 and IMAP retrieve it.

Packet headers carry source and destination addresses, a sequence number and error-checking data; the payload holds the actual user data.

CSMA/CD detects collisions on a shared medium and retransmits after a random back-off; CSMA/CA avoids collisions by signalling intent before transmitting.

A VPN creates an encrypted tunnel over a public network, giving remote users access as if on the private LAN.

In the fetch phase the contents of the PC go to the MAR, memory returns the instruction via the MDR to the CIR, and the PC is incremented.

The control unit decodes the opcode in the CIR and asserts signals that select ALU operations, registers and memory read or write.

Immediate addressing holds the operand in the instruction; direct addressing holds the operand's address; indirect addressing holds the address of the address.

A dedicated device controller handles data transfer and raises an interrupt when finished, freeing the CPU to run other processes.

DMA lets a device transfer data to or from memory without CPU involvement per byte, raising throughput for large transfers.

A buffer temporarily holds data during transfer to smooth differences in speed between a fast CPU and a slow peripheral.

Von Neumann architecture shares one memory for instructions and data; Harvard architecture uses separate instruction and data memories, allowing simultaneous access.

Embedded systems typically combine a microprocessor with dedicated memory and I/O for a specific control task, often with real-time constraints.

Adding two n-bit two's complement numbers can overflow when both operands share a sign and the result has the opposite sign.

Binary subtraction is performed by adding the two's complement of the subtrahend; the carry out of the most significant bit is discarded.

A logical shift fills vacated bits with zeros; a circular (rotate) shift moves bits shifted out back in at the other end.

A bitmask uses AND to test or clear bits, OR to set bits and XOR to toggle bits within a binary pattern.

Character codes are stored as binary; a string is a sequence of characters, and its length in bytes depends on the encoding used.

A queue supports enqueue at the rear and dequeue at the front; a priority queue removes the highest-priority item first regardless of arrival order.

A linked list node holds data plus at least one pointer; a doubly linked list adds a previous pointer, allowing traversal in both directions.

Hash table performance depends on a hash function that spreads keys evenly; a poor function creates long chains and degrades lookup toward O(n).