## Algorithms Glossary

**Please turn javascript on.**

also see

maths

- 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
_{1},x_{2}] = {x | x_{1}<=x<=x_{2}}; 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|
^{2}. - 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
_{1},v_{2}>, has a direction,*from*v_{1}*to*v_{2}. - 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
_{1},v_{2}>; 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
^{30}= 1024^{3}. - 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
_{1},x_{2}) = {x|x_{1}≤x<x_{2}}, and (x_{1},x_{2}] = {x|x_{1}<x≤x_{2}}; 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
^{10}= 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
^{20}= 1024^{2}. - 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
^{2}). - Open interval, (x
_{1},x_{2}) = {x | x_{1}<x<x_{2}}; 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
_{1},v_{2}>, <v_{2},v_{3}>, ..., <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
^{2}, short for S×S. - S
^{*}= {}+S+S^{2}+S^{3}+... - S
^{+}= S+S^{2}+S^{3}+... - 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|
^{2}. - 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
_{1},v_{2}), have no sense of direction, (v_{1},v_{2}) is equivalent to (v_{2},v_{1}). - 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^{2}+7x is Θ(3x^{2}+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
^{2}<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
^{0}= 1 - a
^{1}= 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
_{2}(0.25) = -2 - log
_{2}(0.5) = -1 - log
_{2}(1,024) = 10 - log
_{2}(1,048,576) = 20 - log
_{10}(1,000) = 3 - log
_{10}(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^{2}+...+x^{n}= (1-x^{n+1})/(1-x) if x≠1

∑_{i>=0}x^{i}= 1/(1-x) if |x|<1 - Arithmetic-geometric progression and series,

1+2x+3x^{2}+...+nx^{n-1}= (1-(n+1)x^{n}+nx^{n+1})/(1-x)^{2}if x≠1,

∑_{i>=1}i*x^{i-1}= 1/(1-x)^{2}if |x|<1, e.g., 1+2/2+3/4+4/8+5/16+... = 4, take x=1/2

**Please turn javascript on.**