Algorithms and Data Structures Glossary (Starting with "A")
By
www.nist.gov,
Gaithersburg, Maryland, U.S.A.
paul
. black [at] nist . gov
http://www.nist.gov/dads
Become a member of TranslationDirectory.com at just
$12 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
A
 absolute performance guarantee
 abstract data type
 (a,b)tree
 accepting state
 Ackermann's function
 active data structure
 acyclic directed graph: see directed acyclic graph
 acyclic graph
 adaptive heap sort
 adaptive Huffman coding
 adaptive kd tree
 adaptive sort
 addresscalculation sort
 adjacencylist representation
 adjacencymatrix representation
 adjacent
 admissible vertex
 ADT: see abstract data type
 adversary
 AhoCorasick
 algorithm
 algorithm BSTW
 algorithm FGK
 algorithmically solvable: see decidable problem
 all pairs shortest path
 all simple paths
 alphabet
 Alpha Skip Search algorithm
 alternating path
 alternating Turing machine
 alternation
 American flag sort
 amortized cost
 ancestor
 and
 ANSI
 antichain
 antisymmetric
 ApostolicoCrochemore
 ApostolicoGiancarlo algorithm
 approximate string matching: see string matching with errors
 approximation algorithm
 arborescence
 arc: see edge
 arithmetic coding
 array
 array index
 array merging
 array search
 articulation point: see cut vertex
 assignment problem
 association list: see dictionary
 associative
 associative array
 asymptotically tight bound
 asymptotic bound
 asymptotic lower bound
 asymptotic space complexity
 asymptotic time complexity
 asymptotic upper bound
 augmenting path
 automaton
 average case
 averagecase cost
 AVL tree
 axiomatic semantics
absolute performance guarantee
(definition)
Definition:
An approximation algorithm will return a solution at most a bounded amount more (or less, as appropriate) than the optimum.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
abstract data type
(definition)
Definition:
A set of data values and associated operations that are precisely specified independent of any particular implementation.
Also known as ADT.
Specialization (... is a kind of me.)
dictionary, stack, queue, priority queue, set, bag.
Note:
Since the data values and operations are defined with mathematical precision, rather than as an implementation in a computer language, we may reason about effects of the operations, relations to other abstract data types, whether a program implements the data type, etc.
One of the simplest abstract data types is the stack. The operations new(), push(v, S), top(S), and popOff(S) may be defined with axiomatic semantics as following.  new() returns a stack
 popOff(push(v, S)) = S
 top(push(v, S)) = v
where S is a stack and v is a value. (The usual pop operation is a combination of top, to return the top value, and popOff, to remove the top value.) Contrast this with the axiomatic semantics definition of a set, a dictionary, or a queue.
From these axioms, one may define equality between stacks, define a pop function which returns the top value in a nonempty stack, etc. For instance, the predicate isEmpty(S) may be added and defined with the following additional axioms.
 isEmpty(new()) = true
 isEmpty(push(v, S)) = false
After Nell Dale <ndale@cs.utexas.edu> May 2001.
Author: PEB
(a,b)tree
(data structure)
Definition:
A search tree with the restrictions that all leaves are at the same depth and all internal nodes have between a and b children, where a and b are integers such that 2 ≤ a ≤ (b+1)/2. The root may have as few as 2 children.
Generalization (I am a kind of ...)
search tree.
Specialization (... is a kind of me.)
Btree with 1 ≤ a.
Note:
After Algorithms and Theory of Computation Handbook, page 418, CRC Press LLC.
Author: PEB
accepting state
(definition)
Definition:
If a finite state machine finishes an input string and is in an accepting state, the string is accepted or considered to be valid.
Note:
A machine may enter an accepting state, then leave it. Acceptance depends on whether the machine finishes in an accepting state.
Author: PEB
Ackermann's function
(algorithm)
Definition:
A function of two parameters whose value grows very fast.
Formal Definition:
 A(0, j)=j+1 for j ≥ 0
 A(i, 0)=A(i1, 1) for i > 0
 A(i, j)=A(i1, A(i, j1)) for i, j > 0
Note: Many people have defined other similar functions
which are not simply a restating of this one.
In 1928, Wilhelm Ackermann observed that A(x,y,z),
the zfold iterated exponentiation of x with y, is
a recursive function that is not primitive recursive.
A(x,y,z) was simplified to a function of 2 variables
by Rózsa Péter in 1935. Raphael M. Robinson
simplified the initial condition in 1948.
Author: PEB
More information
Robert Munafo's Versions of Ackermann's Function and analysis. Cowles and Bailey Several Versions of Ackermann's function.
Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen 99(1):118133, December 1928. doi:10.1007/BF01459088
The formal definition given here is G_{n}x in the first page of Raphael M. Robinson, Recursion and Double Recursion, Bulletin of the American Mathematical Society 54:987993, October 1948. doi:10.1090/S000299041948091212
active data structure
(data structure)
Definition:
A data structure with an associated thread or process that performs internal operations to give the external behavior of another, usually more general, data structure.
Also known as functional data structure.
Note:
For example, a queue is usually considered to be unbounded. However, actual queues provided by the hardware or operating system may be significantly limited. Changing the writing and reading processes to use a bounded queue makes those applications more complicated. However, an active queue can accept input from the writer through a system queue, and save items in memory or on disk if the system queue for the reader is full. When the reader's queue has space, items can be retrieved and put back in the queue. Although there are now three components, rather than just the writer and reader, the high level abstraction is very simple and clear.
Author: PEB
acyclic graph
(definition)
Definition:
A graph with no path that starts and ends at the same vertex.
Generalization (I am a kind of ...)
graph.
Specialization (... is a kind of me.)
directed acyclic graph, tree.
Note:
An acyclic undirected graphic is like a tree.
Author: PEB
adaptive heap sort
(algorithm)
Definition:
A variant of heapsort that uses a randomized binary search tree (RBST) to structure the input according to any preexisting order. The RBST is used to select candidates that are put into the heap so the heap doesn't need to keep track of all elements.
Author: IR
More information
C. Levcopoulos and O. Petersson, Adaptive Heapsort, J. of Algorithms 14:395413, 1993.
adaptive Huffman coding
(algorithm)
Definition:
A nearminimal variablelength character coding that changes based on the frequency of characters processed. As characters are processed, frequencies are updated and codes are changed (or, the coding tree is modified).
Also known as dynamic Huffman coding.
Generalization (I am a kind of ...)
Huffman coding.
Specialization (... is a kind of me.)
Vitter's algorithm, algorithm FGK.
Note:
The total message length can be less than that produced by a static Huffman coding since the coding can be different at different places in the message.
Author: PEB
More information
Explanation of algorithm FGK and Vitter's Algorithm (algorithm V), two different adaptive Huffman coding algorithms.
adaptive kd tree
(data structure)
Definition:
A tree for multidimensional points where successive levels may be split along different dimensions.
Note:
After [GG98].
Author: PEB
adaptive sort
(definition)
Definition:
A sorting algorithm that can take advantage of existing order in the input, reducing its requirements for computational resources as a function of the disorder in the input.
Note:
From Algorithms and Theory of Computation Handbook, page 323, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
addresscalculation sort
(algorithm)
Definition:
A sort algorithm which uses knowledge of the domain of the items to calculate the position of each item in the sorted array.
Author: SKS
adjacencylist representation
(data structure)
Definition:
A representation of a directed graph with n vertices using an array of n lists of vertices. List i contains vertex j if there is an edge from vertex i to vertex j. A weighted graph may be represented with a list of vertex/weight pairs. An undirected graph may be represented by having vertex j in the list for vertex i and vertex i in the list for vertex j.
Note:
Suppose we have a directed graph with four vertices. Here are adjacencymatrix and adjacencylist representations. The arrow (>) means a link in a list.
1 2 3 4 1 1 1 1 1 2 1 0 0 0 3 0 1 0 1 4 0 1 1 0
1 > 1 > 2 > 3 > 4 2 > 1 3 > 2 > 4 4 > 2 > 3 One variant is to have an array of columns, rather than rows, with the list going "down". The adjacencylist representation is more compact for a sparse matrix.
Authors: BB,PEB
adjacencymatrix representation
(data structure)
Definition:
A representation of a directed graph with n vertices using an n × n matrix, where the entry at (i,j) is 1 if there is an edge from vertex i to vertex j; otherwise the entry is 0. A weighted graph may be represented using the weight as the entry. An undirected graph may be represented using the same entry in both (i,j) and (j,i) or using an upper triangular matrix.
Aggregate parent (I am a part of or used in ...)
graph.
Note:
Suppose we have a directed graph with four vertices. Here are adjacencymatrix and adjacencylist representations. The arrow (>) means a link in a list. 1 2 3 4 1 1 1 1 1 2 1 0 0 0 3 0 1 0 1 4 0 1 1 0 1 > 1 > 2 > 3 > 4 2 > 1 3 > 2 > 4 4 > 2 > 3 The adjacencylist representation is more compact for a sparse matrix.
Author: SKS
adjacent
(definition)
Definition:
Two vertices of a graph are adjacent if there is an edge between them. Two edges of a graph are adjacent if they connect the same vertex.
Generalization (I am a kind of ...)
binary relation.
Note:
The "adjacent" relation is symmetric, but not (necessarily) reflexive or transitive.
Author: PEB
admissible vertex
(definition)
Definition:
See the explanation at path system problem.
Note:
From Algorithms and Theory of Computation Handbook, page 4523, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
adversary
(definition)
Definition:
A theoretical agent that uses information about the past moves of an online algorithm to choose inputs that force the worstcase cost of the algorithm.
Note:
From Algorithms and Theory of Computation Handbook, page 1017, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
AhoCorasick
(algorithm)
Definition:
A multiple string matching algorithm that constructs a finite state machine from a pattern (list of keywords), then uses the machine to locate all occurrences of the keywords in a body of text.
Generalization (I am a kind of ...)
string matching.
Note:
Construction of the machine takes time proportional to the sum of the lengths of the keywords. The machine is used to process the text string in a single pass. The number of transitions made by the machine is independent of the number of keywords.
Author: VO
More information
Alfred V. Aho and Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, CACM, 18(6):333340, June 1975.
algorithm
(definition)
Definition:
A computable set of steps to achieve a desired result.
Specialization (... is a kind of me.)
probabilistic algorithm, randomized algorithm, deterministic algorithm, nondeterministic algorithm, online algorithm, offline algorithm, oblivious algorithm, external memory algorithm, heuristic.
Note:
The word comes from the Persian author Abu Ja'far Mohammed ibn Mûsâ alKhowârizmî who wrote a book with arithmetic rules dating from about 825 A.D.
Author: PEB
More information
The Analysis of Algorithms web site.
algorithm FGK
(algorithm)
Definition:
An adaptive Huffman coding scheme. Coding is never much worse than twice optimal.
Generalization (I am a kind of ...)
adaptive Huffman coding.
Author: PEB
More information
survey of data compression
Donald E. Knuth, Dynamic Huffman Coding, Journal of Algorithms, 6(2):163180, June 1985.
all pairs shortest path
(classic problem)
Definition:
Find the weight (or length) of the shortest paths between all pairs of vertices in a weighted, directed graph.
Note:
The problem is to find the weights of the shortest paths between all pairs of vertices. For a map, it is to produce the (shortest) road distances between all cities, not which roads to take to get from one city to another. After LK.
Author: PEB
all simple paths
(classic problem)
Definition:
Find all simple paths from a starting vertex (source) to a destination vertex (sink) in a directed graph. In an undirected graph, find all simple paths between two vertices.
Note:
The paths may be enumerated with a depthfirst search. The search can avoid repeating vertices by marking them as they are visited in the recursion, then removing the mark just before returning from the recursive call.
Author: PEB
alphabet
(definition)
Definition:
The set of all possible symbols in an application. For instance, input characters used by a finite state machine, letters making up strings in a language, or symbols in a pattern element. In some cases, an alphabet may be infinite.
Note:
An alphabet may be as simple as the booleans 1 and 0, or as rich as the key words and token types in a programming language.
Author: PEB
alternating path
(definition)
Definition:
A path with alternating free and matched edges.
Note:
From Algorithms and Theory of Computation Handbook, page 73, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
alternating Turing machine
(definition)
Definition:
A nondeterministic Turing machine having universal states, from which the machine accepts only if all possible moves out of that state lead to acceptance.
Note:
From Algorithms and Theory of Computation Handbook, page 2418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
alternation
(definition)
Definition:
A model of computation proposed by A. K. Chandra, L. Stockmeyere, and D. Kozen, which has two kinds of states, AND and OR. The definition of accepting computation is adjusted accordingly.
Note:
First proposed as a model for parallel computation, it has been widely used to prove complexity bounds on problems.
Author: SKS
More information
A. K. Chandra and L. J. Stockmeyer, Alternation, pages 98108, and D. Kozen, On Parallelism in Turing Machines, pages 8997, both in Proc. Seventeenth Annual IEEE Symposium on Foundations of Computer Science, 1976.
American flag sort
(algorithm)
Definition:
An efficient, inplace variant of radix sort that distributes items into hundreds of buckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step. The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes". Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
Note:
This works especially well when sorting a byte at a time, using 256 buckets.
Author: PEB
More information
The flag of the United States of America.
Peter M. McIlroy, Keith Bostic, and M. Douglas McIlroy, Engineering Radix Sort, Computing Systems, 6(1):527, 1993.
amortized cost
(definition)
Definition:
The theoretical speed of a given set of operations. It is O(f(n)) when the execution time of the worst case of all sequences of n operations never exceeds O(n*f(n)).
Note:
The term "amortized worst case" is sometimes used to emphasize that the worst case of a set of operations is averaged.
Author: CLK
More information
R. E. Tarjan, Amortized computational complexity, SIAM Journal on Algebraic and Discrete Methods, 6(2):306318, 1985.
ancestor
(definition)
Definition:
A parent of a node in a tree, the parent of the parent, etc.
Author: PEB
and
(definition)
Definition:
Conjunction: 0 AND 0 = 0, 0 AND 1 = 0, 1 AND 0 = 0, 1 AND 1 = 1.
Author: PEB
ANSI
(definition)
Definition:
American National Standards Institute.
Note:
From Algorithms and Theory of Computation Handbook, pages 2014 and 2025, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
antichain
(definition)
Definition:
A subset of mutually incomparable elements in a poset.
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
antisymmetric
(definition)
Definition:
A binary relation R for which a R b and b R a implies a = b.
Note: The relation "less than or equal to" is
antisymmetric: if a ≤ b and b ≤ a, then a=b.
The relation "is married to" is symmetric, but not
antisymmetric: if Paul is married to Marlena, then
Marlena is married to Paul (symmetric), but Paul and
Marlena are not the same person.
Equals (=) is antisymmetric because a = b and b = a implies a = b. Less than (<) is also antisymmetric because a < b and b < a is always false, and false implies anything.
Author: PEB
approximation algorithm
(algorithmic technique)
Definition:
An algorithm to solve an optimization problem that runs in polynomial time in the length of the input and outputs a solution that is guaranteed to be close to the optimal solution. "Close" has some welldefined sense called the performance guarantee.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
arborescence
(definition)
Definition:
Informally, a directed tree.
Note: Arborescence
Author: PEB
arithmetic coding
(algorithm)
Definition:
A minimal variablelength message coding based on the frequency of each character. The message is represented by a fraction which is the repeated offsetplusproduct reduction of the range (offset) and probability (product) of each character.
Note:
ShannonFano is a minimal prefix code. Huffman is optimal for character coding (one characterone code word) and simple to program. Arithmetic coding is even more compact, since it can allocate fractional bits, but is more complicated and patents cover some uses. Range encoding is essentially the same, but uses integers and integer ranges instead of fractions. The implementation in Martin 1979 is thought to not be covered by patents.
Author: PEB
More information
An introduction to data compression methods. Wikipedia entries for Arithmetic coding and Range encoding.
Ian H. Witten, Radford M. Neal, and John G. Cleary, Arithmetic Coding for Data Compression, CACM 30(6):520540, June 1987. G. N. N. Martin, Range encoding: an algorithm for removing redundancy from a digitised message, Video & Data Recording Conference, Southampton, UK, July 1979.
array
(data structure)
Definition:
An assemblage of items that are randomly accessible by integers, the index.
Formal Definition: Ignoring size an array may be seen as an abstract data type with the operations new(), set(i, v, A), and get(i, A), where i is a numeric index, v is a value, and A is an array. The operations may be defined with axiomatic semantics as follows.
 new() returns an array
 get(i, set(i, v, A)) = v
 get(i, set(j, v, A)) = get(i, A) if i ≠ j
Compare this with a dictionary using integers as keys. If the contents of a new array are set to some implicit initial value v_{i}, we could add the following rule for get.
 get(i, new()) = v_{i}
Typically arrays have a fixed size and use either 0based indexing or onebased indexing. Fixed initial size and 0based indexing may incorporated as follows.
 new(s) returns an array, which has a size s
 size(new(s)) = s
 size(set(i, v, A)) = size(A)
 get(i, set(i, v, A)) = v if 0 ≤ i < size(A)
 get(i, set(j, v, A)) = get(i, A) if i ≠ j
Onebased or other indexing may be defined similarly.
Specialization (... is a kind of me.)
dynamic array, sorted array.
Aggregate child (... is a part of or used in me.)
array index, onebased indexing, 0based indexing.
Note: An unordered array must be searched with
a linear search. Average search time may be improved
using a movetofront heuristic in some cases. An
external index, such as a hash table or inverted index
may help make an array search quicker and speed overall
processing if the array is not changed often. If the
array is kept sorted, a binary search or interpolation
search is faster.
Inserting into an array takes Θ(n) time. If that's too slow, use a balanced tree, skip list, or a linked list. Knuth uses a balanced tree with a RANK field that supports Θ(log n) access by index and Θ(log n) insert and delete. [Knuth98, 3:471, Sect. 6.2.3]
If it takes too long to initialize a big array of size S, a huge sparse array takes time proportional to the number of accesses and only Θ(S) extra space.
Author: PEB
More information
Jennifer E. Elaan's fast array algorithm, equivalent to Knuth's.
array index
(definition)
Definition:
The location of an item in an array.
Aggregate child (... is a part of or used in me.)
onebased indexing, 0based indexing.
Note:
In most programming languages, the first array index is 0 or 1, and indexes continue through the natural numbers. The upper bound of an array is generally language and possibly system specific.
Author: PR
array merging
(algorithm)
Definition:
Joining two arrays into one.
Author: PR
array search
(classic problem)
Definition:
Find an element in an array. Various algorithms exist which require more or less structure in the array elements or implementation.
Note:
An external index, such as a hash table or inverted index may help make the search quicker and speed overall processing if the array is not changed often.
Author: PR
assignment problem
(classic problem)
Definition:
The problem of finding a maximum (or minimum) weight matching in a weighted, bipartite graph.
Also known as marriage problem.
Note:
From Algorithms and Theory of Computation Handbook, page 721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
associative
(definition)
Definition:
A function where f(A, f(B, C)) = f(f(A, B), C).
Note:
Multiplication is associative, e.g., 2 × (3 × 4) = (2 × 3) × 4, and commutative, e.g., 2 × 3 = 3 × 2. Subtraction is neither associative, e.g., 2  (3  4) ≠ (2  3)  4, nor commutative, e.g., 2  3 ≠ 3  2. Because of rounding floating point addition on a computer is not associative, e.g., (1000000 + .00001) + .00001 ≠ 1000000 + (.00001 + .00001) (actual values depend on the details of the computer addition), but is commutative, e.g., 1000000 + .00001 = .00001 + 1000000. Cartesian product is associative, e.g., {1, 2} × ({a, b} × {X, Y}) = ({1, 2} × {a, b}) × {X, Y}, but is not commutative, e.g., {1, 2} × {a, b} ≠ {a, b} × {1, 2}.
Author: PEB
associative array
(data structure)
Definition:
A collection of items that are randomly accessible by a key, often a string.
Note:
Implementation: the access method must essentially search for a match. The simplest, but slowest, implementation is to do a linear search over the array for a match.
If that is too slow, and you access the array by number, too, you must create and maintain an index into the array. The index is a dictionary, organized by the content, of indexes into the array.
Author: PEB
asymptotically tight bound
(definition)
Definition:
When the asymptotic complexity of an algorithm exactly matches the theoretically proved asymptotic complexity of the corresponding problem. Informally, when an algorithm solves a problem at the theoretical minimum.
Author: SKS
asymptotic bound
(definition)
Definition:
A curve representing the limit of a function. That is, the distance between a function and the curve tends to zero. The function may or may not intersect the bounding curve.
Note:
After Ben Podoll <benjamin.podoll@und.nodak.edu> 28 August 2003.
Author: PEB
asymptotic lower bound
(definition)
Definition:
An asymptotic bound, as function of the size of the input, on the best (fastest, least amount of space used, etc.) an algorithm can possibly achieve to solve a problem. That is, no algorithm can use fewer resources than the bound.
Author: SKS
asymptotic space complexity
(definition)
Definition:
The limiting behavior of the use of memory space of an algorithm when the size of the problem goes to infinity. This is usually denoted in bigO notation.
Note:
From Algorithms and Theory of Computation Handbook, page 1926, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
asymptotic time complexity
(definition)
Definition:
The limiting behavior of the execution time of an algorithm when the size of the problem goes to infinity. This is usually denoted in bigO notation.
Note:
From Algorithms and Theory of Computation Handbook, page 1926, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
asymptotic upper bound
(definition)
Definition:
An asymptotic bound, as function of the size of the input, on the worst (slowest, most amount of space used, etc.) an algorithm will do to solve a problem. That is, no input will cause the algorithm to use more resources than the bound.
Author: SKS
augmenting path
(definition)
Definition:
A path with alternating free and matched edges that begins and ends with free vertices. Used to augment (improve or increase) a matching or flow.
Note:
From Algorithms and Theory of Computation Handbook, page 73, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
automaton
(definition)
Definition:
See finite state machine or cellular automaton.
Author: PEB
average case
(definition)
Definition:
Having to do with the mathematical average of all cases.
Note:
Deciding whether the average is mean, median, or mode, and what are all expected or reasonable cases can be difficult.
Author: PEB
More information
Average Case Complexity Forum
averagecase cost
(definition)
Definition:
The sum of costs of an algorithm over all possible inputs divided by the number of possible inputs.
Note:
From Algorithms and Theory of Computation Handbook, page 126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
More information
Average Case Complexity Forum
AVL tree
(data structure)
Definition:
A balanced binary search tree where the height of the two subtrees (children) of a node differs by at most one. Lookup, insertion, and deletion are O(log n), where n is the number of nodes in the tree.
Generalization (I am a kind of ...)
heightbalanced tree, balanced binary tree, binary search tree, redblack tree (when colored).
Aggregate child (... is a part of or used in me.)
left rotation, right rotation.
Note:
The structure is named for the inventors, AdelsonVelskii and Landis. If necessary, the tree is rebalanced after insertions or deletions using rotations. After Gary Grubb <ggrubb@sr.hp.com>. An AVL tree is at least as balanced as a redblack tree.
Author: PEB
More information
explanation and example.
Georgii M. AdelsonVelskii and Evgenii M. Landis, An algorithm for the organization of information, Doklady Akademii Nauk SSSR, 146:263266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:12591263, 1962. (Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)
axiomatic semantics
(definition)
Definition:
Defining the behavior of an abstract data type with axioms.
Aggregate parent (I am a part of or used in ...)
stack, bag, dictionary, priority queue, queue, set, cactus stack.
Note:
For example, the abstract data type stack has the operations new(), push(v, S) and popOff(S), among others. These may be defined with the following axioms.  new() returns a stack
 popOff(push(v, S)) = S
 top(push(v, S)) = v
where S is a stack and v is a value. What does this mean? The first axiom says all we know about new() is that it returns a stack. Informally, we know it returns an empty stack, but "empty" is a concept we would have to define. So we leave it. The second axiom says that if we push a value onto a stack then pop it off, the result is the same stack. The "=" can be seen as a rewrite operation. The axiom "X = Y" means any time we see X, we can rewrite it to be Y. X may contain variables representing subexpressions. What is the meaning of "popOff(push(1776, new()))"? The second axiom says it means the same as new(). The third axiom assigns meaning to expressions like top(push(1, push(2, new()))): it is 1. This is reasonable, since the top element is the latest one pushed. A series of push and popOff operations and a top operation may be reduced with these axioms. What stack does new() return, then? We still haven't said; top(new()) is just not defined. But that is how a stack works: the top of an empty stack is not defined. So our formalism corresponds to our mental notion of a stack. If we want to, we can add more axioms for richer semantics, as is done in the stack entry.
Author: PEB
Published  April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here  Free!
Freelance translators are welcome to register here  Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
