Algorithms Glossary

LA home

also see
  • 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.

  • 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 [x1,x2] = {x | x1<=x<=x2}; 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, <v1,v2>, has a direction, from v1 to v2.
  • 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 <v1,v2>; 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., Zp 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 = 230 = 10243.
  • 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, [x1,x2) = {x|x1≤x<x2}, and (x1,x2] = {x|x1<x≤x2}; 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 ST, 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 = 210 = 1024
  • Kn, the complete (undirected) graph on n vertices.
  • Km,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 = 220 = 10242.
  • 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(x2).
  • Open interval, (x1,x2) = {x | x1<x<x2}; 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 <v1,v2>, <v2,v3>, ..., <vn-1,vn>.
  • 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.
  • S2, short for S×S.
  • S* = {}+S+S2+S3+...
  • S+ = S+S2+S3+...
  • 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., (v1,v2), have no sense of direction, (v1,v2) is equivalent to (v2,v1).
  • Union of two sets, ST, 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.
  • Zp, 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. x2+7x is Θ(3x2+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 & x2<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.

  • a0 = 1
  • a1 = a
  • a-x = 1/ax
  • ax+y = ax * ay
  • ax y = ax*y = (ax)y

  • factorial(n) = n! = n*(n-1)*...*1,  e.g., 4! = 4*3*2*1 = 24; also see Stirling's approximation.

  • logb(x) = y where by=x
  • logb(x*y) = logb(x)+logb(y)
  • loga(x) = logb(x)/logb(a)
  • loga(b) = 1/logb(a)
  • logb(1) = 0 for all b
  • logb(b) = 1
  • log2(0.25) = -2
  • log2(0.5) = -1
  • log2(1,024) = 10
  • log2(1,048,576) = 20
  • log10(1,000) = 3
  • log10(1,000,000) = 6
  • ln(x) = loge(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+x2+...+xn = (1-xn+1)/(1-x) if x≠1
    i>=0 xi = 1/(1-x) if |x|<1
  • Arithmetic-geometric progression and series,
    1+2x+3x2+...+nxn-1 = (1-(n+1)xn+nxn+1)/(1-x)2 if x≠1,
    i>=1 i*xi-1 = 1/(1-x)2 if |x|<1, e.g., 1+2/2+3/4+4/8+5/16+... = 4, take x=1/2

© L. Allison   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Sunday, 20-Apr-2014 16:01:59 EST.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.