Glossary

Algorithms Glossary

Acyclic, of a graph, 'having no cycles'; see cycle and DAG.
Adjacent, as in vertices of a graph, w is adjacent to v if there is an edge <v,w>; see connected.
Application of a function, e.g., as in: hcf m n.
Assertion, a true statement about, or a condition of, the state of a program's variables at a certain point in the program.
Arc of a graph, direct connection between two vertices; see edge.
Atom, indivisible value especially when the element of a list.
AVL tree, height balanced binary tree.
B-tree of order k (not a binary tree!) each internal node can hold k-1 keys and (pointers to) k subtrees; ordered left to right; is height-balanced.
Binary recursion, where an activation of a subprogram may call the subprogram twice.
Binary search, to search by successive division into two equal parts.
Binary search tree, elements in left subtree < root < elements in right subtree & all subtrees also satisfy this condition.
Binary tree, a tree where each node has 0, 1 or 2 child nodes (subtrees); also see strict binary tree.
BWT, Burrows Wheeler Transform, a certain very useful permutation of a string.
Clique, a subgraph (of an undirected graph) having an edge from each vertex to every other vertex.
Closed interval [x₁,x₂] = {x | x₁<=x<=x₂}; see open interval.
Collision, when two keys hash to the same value.
Complete binary tree, a full binary tree where all leaf nodes are at level 'n' or 'n-1', and all gaps, if any, are in level n at the right; also see perfect binary tree.
Complete undirected graph, one having an edge between each pair of vertices (so it is a clique).
Completely connected (undirected) graph; see connected graph.
Complexity, amount of time or space an algorithm uses.
Composition, f.g, of two functions f and g, (f.g)(x)=f(g x).
Conjunction, as in p&q&...&r.
Connected, as in vertices of a graph, vertex w is connected to vertex v if there is a path from v to w.
Connected, an undirected graph is connected if there is a path from each vertex to every other vertex.
Cons, constructor of a data type, especially of lists, sometimes infix '.' as in 'h.t' in functional languages.
Continuation, a routine, c, passed as a parameter to a subroutine, p, to continue on from or to be the last thing that p calls.
Cycle, a path (see path) in a graph where the 1st and last vertices in the path are the same.
DAG, directed acyclic graph, i.e., no cycles.
Dense graph, one where |E|~|V|².
Dense type, where a large fraction of the set of potential values is in use.
Digraph, abbreviation for directed graph.
Directed graph, graph where each edge, <v₁,v₂>, has a direction, from v₁ to v₂.
Disjoint union, S+T, of sets S and T is the set of 'tagged union' elements from S or T.
Disjunction, as in p or q or ... or r.
Dynamic programming, a certain problem solving strategy.
Edge of a graph, direct connection between two vertices, specified by giving the two vertices <v₁,v₂>; see arc.
Eigen-value, and Eigen-vector, of a matrix, M, a value, λ, and a vector, v, s.t. Mv=λv.
Field, a set with operations '+' and '*' where the "usual laws" of (+,-,*,=) hold, e.g., Z_p the integers modulo p.
FIFO, first in first out - queue.
Fixed-point, of a function, f, a value x such that f(x)=x.
Full binary tree, where every node has either zero or two children (having one child is not allowed).
G, giga, 1G = 2³⁰ = 1024³.
Gamma (Γ) function, Γ(x+1) generalises factorial(x), and Γx=(x-1)!.
Graph, <V,E>, a set of vertices V, and a set of edges E.
Graph Isomorphism Problem.
Group, a set of elements with an associative binary operation, closed, with an identity and inverses.
Half open interval, [x₁,x₂) = {x|x₁≤x<x₂}, and (x₁,x₂] = {x|x₁<x≤x₂}; also see closed, and open interval.
Hash, to map a sparse index type onto a range of (usually) integers.
hd, short for head (first element), as in the head of a (linked-) list.
Head of a list, first element of the list.
Heap, see section on heap sort.
Height balanced tree, e.g., AVL-tree, |h(left)-h(right)| <= 1, also for subtrees.
Iff, if and only if, <=> (⇔).
Implies, => (⇒), e.g., p=>q, q must be true whenever p is true, equivalent to 'not p or q'.
Infix operator, e.g., the '+' in x+y.
Infix traversal of a tree, infix(left); node; infix(right).
Intersection of two sets, sometimes written S*T, or S∩T, or even S.T, set of elements that are in both S and T.
Interval of an array, A[i..j] consists of A[i], A[i+1], ..., A[j] if i<=j, and is empty otherwise.
Interval of the real line - see open interval and closed interval.
Invariant of loop, a condition true at the start of every iteration; when (if) the loop terminates you have the conjunction of the invariant & the negation of the loop test.
K, kilo, 1K = 2¹⁰ = 1024
K_n, the complete (undirected) graph on n vertices.
K_m,n, the complete (undirected) bipartite graph on m+n vertices.
Key, unique identifier, number or other identifying attribute of an entity or thing.
Leaf, a node of a tree having no subtrees (or only empty ones).
Lexicographical, as in lexicographical order, generalizes alphabetical order, e.g., "abbey"<"able", "a"<"aardvark", "123"<"45", and "001.642 KNU 1:2"<"005.1 K74A"
LIFO, last in first out - stack.
Linear recursion, where an activation of a subprogram may call the subprogram once.
Linear search, to search sequentially, 1st, 2nd, 3rd,....
List, sequence of linked cells.
Loop, often as self-loop, in a graph, an edge <v,v>, not allowed in some graphs, but allowed, e.g., in finite state automata (FSA).
Lyndon word, a word (string) that is strictly lexically (alphabetically) less than all of its cyclic rotations.
M, mega, 1M = 2²⁰ = 1024².
Method, object-oriented speak for subroutine, function or procedure.
Mutual recursion of x and y, where x refers to y and y to x.
Nil, special pointer value, empty list.
Node, vertex of tree or graph.
Null, (i) adj., empty, (ii) test for the empty or nil list, (iii) the nil pointer in C and its relatives.
O( ), dominant term or long term behaviour (complexity) of a function; f is O(g) if there exist constants m>=0 and c>0 s.t. |f(n)|<=c*g(n) for all n>=m (see Knuth 1976).
o( ), f is o(g) if f is O(g) and f is not Θ(g). E.g. x is o(x²).
Open interval, (x₁,x₂) = {x | x₁<x<x₂}; see closed interval.
Parse, to check grammatical correctness of a sentence.
Parse tree, a tree showing the grammatical structure of a syntactically correct sentence.
Partition, of an integer, e.g., 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1.
Partition, of a set S, a collection of disjoint subsets of S whose union is S.
Partition operation, as in quick sort, to divide (all or part of) an array a[0..n-1] into two or more parts a[0..i-1], a[i..j-1], ..., a[k..n-1].
Path in a graph, a sequence of edges <v₁,v₂>, <v₂,v₃>, ..., <v_n-1,v_n>.
Perfect binary tree, a complete binary tree where all leaf nodes are at level 'n'.
Polish notation, prefix operator sequence, after Jan Lukasiewicz [-- Knuth].
Pop, to remove an element from a stack.
Postcondition, a condition true after a statement or subprogram is executed.
Postfix operator, e.g., the + in x y +, also known as reverse Polish.
Postfix traversal of a tree, postfix(left); postfix(right); node.
Precondition, necessary condition for statement or subprogram to work correctly.
Predicate, a test, a condition, a function returning a Boolean result, e.g., 'odd', 'prime'.
Prefix of a string s[1..n] is any s[1..i], i in [1..n], or in [0..n] if you allow the empty prefix; also see suffix.
Prefix operator, e.g., the + in + x y.
Prefix traversal of a tree, node; prefix(left); prefix(right).
Priority queue, a structure where items can be added with a given priority and the highest-priority element can be (quickly) removed.
Probe, a strategy to deal with hash collisions.
Procedure, usually, a subroutine that returns no result.
Propositional logic.
Push, to place an element in a stack.
Quaternions, a generalization of complex numbers useful in 3D-rotations, say.
Queue, a FIFO data type.
Random access, to access elements in an unpredictable order.
Recursion, where a type or a subprogram makes use of its own definition; see recursion.
Reverse Polish, postfix operator sequence; see Polish notation.
Routine, a subroutine, function, procedure or method.
S+T, the (disjoint) union of two sets or types, S and T; see union.
S×T, the 'product' of sets or types S and T, the set or type of pairs <s,t> such that s in S and t in T.
S², short for S×S.
S^* = {}+S+S²+S³+...
S⁺ = S+S²+S³+...
S->T, see ->.
Search tree, (usually) binary tree with elements ordered left to right.
Segment of an array - see interval of an array.
Self-loop, see loop.
Sequential access, to access elements in some fixed order, e.g., alphabetic, or by position in a data structure.
Space complexity, amount of space an algorithm uses, and in particular how this varies with the size, or some other property, of the data.
Spanning tree of a graph G, a subgraph which is a tree, contains all vertices of G; edges form a subset of the edges of G.
Sparse graph, one where |E| << |V|².
Sparse type, where the set of potential values is much bigger than the set of values in actual use, e.g., String.
Stable, a sorting algorithm is stable if the relative order of two elements with the same key is not changed by the algorithm.
Stack, a LIFO data type.
Stirling's approximation -- to log n!.
Strict binary tree, a binary tree where each node has 0 or 2 (never 1) child nodes (subtrees).
Strongly connected, a directed graph is s.c. if there is a path from each vertex, v, to every other vertex, w (and hence also a path from w to v).
Subgraph Isomorphism Problem.
Subroutine, a function, procedure or method.
Suffix of a string s[1..n] is any s[i..n], i in [1..n], or in [1..n+1] if you allow the empty suffix; also see suffix tree, and prefix.
Suffix array, efficiently sorted array of (pointers to) the suffices of a string.
Suffix tree, holds the sorted suffices of a string.
Tail of a list, everything but the first element of the list, itself a list; also known as next, rest etc..
Ties, as in 'break ties arbitrarily', if two or more solutions are optimal then pick one of them arbitrarily.
Time complexity, amount of time an algorithm takes, and in particular how this varies with the size, or some other property, of the data.
tl, short for tail, as in the tail of a (linked-) list.
Traverse, to visit each element, cell or node of a list, tree, graph or other data structure.
Tree (binary, rooted), either empty or contains two subtrees and usually also an element.
Tree (unrooted), a connected undirected graph where for any two vertices u and v, there is a unique path from u to v.
Undirected graph, one where the edges, e.g., (v₁,v₂), have no sense of direction, (v₁,v₂) is equivalent to (v₂,v₁).
Union of two sets, S∪T, the set of elements that are in S, or in T, or in both S and T; the disjoint union S+T is the set of "tagged" elements from S or from T.
Vertex, a point in a tree or graph.
Weighted graph, one where each edge has a cost or weight, i.e., edge-weighted; less commonly, can also have a vertex-weighted graph.
wff, well formed formula.
wrt, with respect to.
Z_p, the integers modulo (mod) p, i.e., [0..p-1], is a field if p is a prime number, i.e., the usual laws of (+,-,*,=) hold.
(x,y), 1. the pair (2-tuple) x and y, 2. see open interval.
Θ( ), f is Θ(g) if there exist constants m>=0, c>0 and c'>0 such that c*g(n)<=f(n)<=c'*g(n) for all n>=m. NB. If f()>=0 this is equivalent to f is O(g) and f is Ω(g), and to f is O(g) and g is O(f). E.g. x²+7x is Θ(3x²+5). See O( ).
Ω( ), f is Ω(g) if there exist constants m>=0 and c>0 such that f(n)>=c*g(n) for all n>=m. NB. If g()>=0, this is equivalent to g is O(f). See O( ).
|x|, the size of x, absolute value of x, length of x (string, etc.), number of elements in x (array, set, etc.).
>>, much bigger than, as in x is much bigger than y, x>>y, or y<<x.
<<, much less than, as in y<<x.
{x | P(x)}, set notation, the set of x such that P(x) is true, i.e., the set of x satisfying some condition P, e.g., {x | x:Int & x²<10} = {-3,-2,-1,0,1,2,3}.
{ } the empty set, sometimes written φ.
-> (→), as in T->U, a function type ( U function(T), proc(T)U , etc.), e.g., Int->Int is the type of all integer functions such as factorial:Int->Int. In T->U, T is the type of the input parameter and U is the type of the output result returned by the function.
-> (→) is sometimes used for 'q logically follows from p', as in p->q, e.g., in propositional logic.
=> (⇒), as in p=>q, p implies q, or q<=p, q is implied by p, q must be true whenever p is true, equivalent to (not p or q).
<=> (⇔), as in p<=>q, p iff q, p=>q and q=>p.
¬, logical negation, as in ¬p, etc.
., dot, various uses: logical conjunction p.q (p&q), multiplication n.log(n), function composition f.g, infix list constructor h.t.
=, equality in mathematics and many programming languages, as in 2+2=3+1 (== in C and relatives). Also definition, as in x=e, x is defined to be e.
=, definition, e.g., as in 0! = 1, n! = n*(n-1)!.
== equality operator in C and relatives; also see =.
<> not equal (≠) in some programming languages.
!= not equal (≠) in some programming languages.
>= greater than or equal to (≥), 7>=6 and 7>=7.
<= less than or equal to (≤), but also 'implied by' (⇐) in logic as in q<=p, i.e., p=>q.
:= assignment operator in many programming languages (= in C and relatives).
<- (←), assignment operator in some programming languages.
a⁰ = 1
a¹ = a
a^-x = 1/a^x
a^x+y = a^x * a^y
a^x y = a^x*y = (a^x)^y
factorial(n) = n! = n*(n-1)*...*1, e.g., 4! = 4*3*2*1 = 24; also see Stirling's approximation.
log_b(x) = y where b^y=x
log_b(x*y) = log_b(x)+log_b(y)
log_a(x) = log_b(x)/log_b(a)
log_a(b) = 1/log_b(a)
log_b(1) = 0 for all b
log_b(b) = 1
log₂(0.25) = -2
log₂(0.5) = -1
log₂(1,024) = 10
log₂(1,048,576) = 20
log₁₀(1,000) = 3
log₁₀(1,000,000) = 6
Arithmetic progression, 1+2+...+n = n*(1+n)/2, ∑_i=m..n i = (n-m+1)(m+n)/2.
Geometric progression and series,
1+x+x²+...+xⁿ = (1-xⁿ⁺¹)/(1-x) if x≠1
∑_i>=0 xⁱ = 1/(1-x) if |x|<1
Arithmetic-geometric progression and series,
1+2x+3x²+...+nx^n-1 = (1-(n+1)xⁿ+nxⁿ⁺¹)/(1-x)² if x≠1,
∑_i>=1 i*x^i-1 = 1/(1-x)² if |x|<1, e.g., 1+2/2+3/4+4/8+5/16+... = 4, take x=1/2