VCE Algorithmics (HESS) key terms

A finite, ordered set of unambiguous steps that takes some input, performs operations on it, and produces an output or stops with no solution. It must terminate.

A structured, English-like notation for expressing an algorithm's logic without the strict syntax of a programming language, used to communicate and analyse solutions independently of implementation details.

The property that an algorithm produces the required output for every valid input, not just typical ones. It is established by reasoning or proof, not by testing alone.

The guarantee that an algorithm halts after a finite number of steps for every valid input. It is usually shown with a variant or a strictly decreasing measure.

A statement that is true before a loop begins, remains true after each iteration, and, together with the loop's exit condition, helps prove the algorithm's correctness.

A quantity that strictly decreases (or increases toward a bound) with each loop iteration and cannot decrease forever, used to prove that a loop or algorithm terminates.

A proof technique with a base case showing a claim holds initially and an inductive step showing that if it holds for one stage it holds for the next, used to justify recursive algorithms and loop invariants.

A technique where a function solves a problem by calling itself on smaller instances of the same problem, requiring a base case to stop and a recursive case to reduce the input.

The condition in a recursive definition or algorithm that is solved directly without further recursive calls, preventing infinite recursion and anchoring inductive proofs.

An equation expressing the running time or output size of a recursive algorithm in terms of its smaller subproblems, such as T(n) = 2T(n/2) + n, which is then solved to find complexity.

A measure of how the number of basic operations performed by an algorithm grows as input size increases, usually expressed with asymptotic notation and ignoring constant factors.

A measure of the extra memory an algorithm requires beyond its input as a function of input size, including space for data structures and recursion call stacks.

An asymptotic upper bound describing how a function grows, written f(n) = O(g(n)) when f is eventually bounded above by a constant multiple of g, used to classify algorithm efficiency.

An asymptotic lower bound: f(n) = Ω(g(n)) when f eventually grows at least as fast as a constant multiple of g, used to state best-case or minimum resource requirements.

A tight asymptotic bound: f(n) = Θ(g(n)) when f is bounded both above and below by constant multiples of g, meaning f and g grow at the same rate.

Evaluating an algorithm's resource use on the input of a given size that causes the most work, giving a guarantee that performance never falls below this standard.

Evaluating an algorithm's resource use on the most favourable input of a given size, useful for comparison but rarely a reliable predictor of typical performance.

Evaluating expected resource use across a defined distribution of inputs of a given size, requiring assumptions about which inputs are likely to occur.

An algorithm design strategy that splits a problem into smaller independent subproblems, solves them recursively, and combines their results into a solution for the original problem.

An approach that builds a solution step by step, always choosing the locally best option available, which is fast but only correct when the problem has the right structure.

A technique that solves overlapping subproblems once, stores their results in a table, and reuses them to build up the answer, trading extra memory for reduced computation.

A top-down optimisation where a recursive function caches each computed result so repeated calls with the same arguments return the stored value instead of recomputing it.

The property that an optimal solution to a problem can be constructed from optimal solutions to its subproblems, a precondition for dynamic programming and greedy methods to work.

A straightforward approach that enumerates every possible candidate solution and checks each one, guaranteed to find an answer but often impractically slow on large inputs.

A rule or estimate that guides search toward promising solutions, trading guaranteed optimality for speed, often used when exact methods are too slow.

An algorithm that runs efficiently and returns a solution guaranteed to be within some proven factor of the optimal, used for hard optimisation problems.

A structure of vertices joined by edges, used to model relationships such as networks, maps, and dependencies; edges may be directed or undirected and may carry weights.

A graph representation using a two-dimensional array where entry (i, j) indicates whether an edge connects vertex i to vertex j, allowing fast edge checks but using quadratic space.

A graph representation storing, for each vertex, a list of its neighbours, which uses space proportional to the number of edges and suits sparse graphs.

A systematic procedure for visiting every reachable vertex of a graph or every node of a tree exactly once, forming the basis of search and connectivity algorithms.

A traversal that explores all vertices at the current distance before moving further out, using a queue, and finds shortest paths in unweighted graphs.

A traversal that follows one path as far as possible before backtracking, typically implemented with a stack or recursion, and useful for cycle and connectivity detection.

A method that finds shortest paths from a source to all vertices in a graph with non-negative edge weights by repeatedly finalising the closest unfinalised vertex.

A best-first pathfinding algorithm that ranks partial paths by the cost so far plus an admissible heuristic estimate of the remaining cost, finding optimal paths when the heuristic is admissible.

A last-in-first-out data structure where insertion and removal occur at the same end, used for recursion, backtracking, and depth-first traversal.

A first-in-first-out data structure where items are added at one end and removed from the other, used for scheduling and breadth-first traversal.

An abstract data type that returns the element with highest priority first, supporting efficient insertion and removal of the minimum or maximum, often implemented with a heap.

A tree-based structure satisfying the heap property, where each parent compares favourably with its children, giving efficient access to the extreme element and logarithmic updates.

The open question of whether every problem whose solution can be checked quickly can also be solved quickly, central to classifying problems as tractable or intractable.

A class of decision problems in NP to which every problem in NP can be reduced in polynomial time; finding a fast exact algorithm for any one would solve P versus NP.

A transformation converting instances of one problem into instances of another so that a solution to the second yields a solution to the first, used to compare problem difficulty.

A problem for which no algorithm with polynomial-time complexity in the input size is known, so exact solutions become impractical as inputs grow.

The rapid, often exponential growth in the number of candidate solutions as input size increases, which makes exhaustive search impractical for large instances.