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.
• Breadth first traversal of a tree, visit parent then children then grand children etc.

  © L . A l l i s o n 1 9 8 4

• 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
• ln(x) = log_e(x)
  -- © L.Allison 1984
• 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