Cambridge IAL Computer Science flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Decomposition

Breaking a large problem into smaller sub-problems that can each be solved, tested and maintained independently, with defined interfaces between them.

Abstraction

Removing detail that is irrelevant to the current purpose so a problem can be modelled and solved with only the essential features retained.

Binary search complexity

O(log n) time on a sorted list, because each comparison halves the remaining search space; the list must be sorted before searching.

Merge sort

A divide-and-conquer sort that halves the list, sorts each half recursively and merges sorted halves; O(n log n) time in all cases and needs O(n) extra space.

Recursion base case

The condition that stops a recursive function from calling itself again; without it the recursion never terminates and the call stack overflows.

Finite state machine

A model with a set of states, an input alphabet, transitions between states, a start state and accepting states, with no memory beyond the current state.

Object-oriented encapsulation

Bundling attributes and methods inside a class and restricting direct access to internal state, so it can only be changed through the class's own methods.

Compiler versus interpreter

A compiler translates the whole program to machine code before running it; an interpreter translates and executes line by line, stopping at the first error.

Pass by reference

Passing the memory address of an argument to a subroutine, so changes made inside the subroutine modify the caller's original variable.

Pure function

A function whose output depends only on its inputs and which produces no side effects, so the same arguments always return the same result.

Polymorphism

The ability for the same method name to behave differently for different classes, typically through overriding in subclasses that share a superclass.

Linker

A program that combines compiled object modules and library routines into one executable file, resolving references between modules.

OSI model layers

Seven layers from bottom: physical, data link, network, transport, session, presentation, application; each provides services to the layer above.

TCP versus UDP

TCP is connection-oriented with acknowledgements, retransmission and ordering; UDP is connectionless with no delivery guarantee and lower overhead.

Packet switching

Data is split into packets that are routed independently across shared links and reassembled at the destination, improving link utilisation over circuit switching.

MAC address

A 48-bit hardware address burned into a network interface, used to deliver frames within a local network segment.

Router function

A device that forwards packets between different networks by examining destination IP addresses and choosing the best path from its routing table.

Symmetric encryption

Encryption where sender and receiver share one secret key for both encryption and decryption; fast, but the key must be distributed securely.

Fetch-decode-execute cycle

The CPU repeatedly copies the program counter to the MAR, fetches the instruction into the CIR, increments the PC, decodes and then executes it.

Program counter

A register holding the memory address of the next instruction to be fetched; it is incremented during the fetch phase of the cycle.

Von Neumann bottleneck

The performance limit caused by instructions and data sharing one bus and memory, so the CPU may wait while data is transferred.

RISC architecture

A design using a small set of simple, fixed-length instructions, many registers and pipelining, so most instructions execute in one clock cycle.

Address bus width

The number of address lines determines how many memory locations can be addressed; n lines allow 2^n distinct addresses.

Interrupt

A signal that suspends the current process, saves its state, runs an interrupt service routine and then restores the saved state.

Cache memory

Small, fast memory close to the CPU holding recently used instructions and data to reduce average memory access time.

Two's complement range

For n bits, values run from -2^(n-1) to 2^(n-1)-1; the leftmost bit has place value -2^(n-1) and there is only one representation of zero.

Arithmetic shift right

A right shift that copies the sign bit into vacated positions, dividing a signed binary value by two while preserving its sign.

Stack data structure

A last-in-first-out structure where items are added with push and removed with pop at the same end, the top.

Queue data structure

A first-in-first-out structure where items are added at the rear with enqueue and removed from the front with dequeue.

Linked list

A structure of nodes each holding data and a pointer to the next node; insertion and deletion are cheap but access requires sequential traversal.

Hash collision

When two different keys produce the same hash index; resolved by chaining lists per bucket or by probing for the next free slot.

Floating point mantissa and exponent

A floating point number stores a sign, a mantissa giving significant digits and an exponent giving scale; more mantissa bits mean precision, more exponent bits mean range.