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 k-d tree
- adaptive sort
- address-calculation sort
- adjacency-list representation
- adjacency-matrix representation
- adjacent
- admissible vertex
- ADT: see abstract data type
- adversary
- Aho-Corasick
- 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
- Apostolico-Crochemore
- Apostolico-Giancarlo 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
- average-case 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 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 non-empty 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.)
B-tree with 1 ≤ a.
Note:
After Algorithms and Theory of Computation Handbook, page 4-18, 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(i-1, 1) for i > 0
- A(i, j)=A(i-1, A(i, j-1)) 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 z-fold 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):118-133, December 1928.
doi:10.1007/BF01459088
The formal definition given here is Gnx in the first page of
Raphael M. Robinson, Recursion and Double Recursion, Bulletin of the American Mathematical Society 54:987-993, October 1948.
doi:10.1090/S0002-9904-1948-09121-2
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:395-413, 1993.
adaptive Huffman coding
(algorithm)
Definition:
A near-minimal variable-length 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 k-d 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 3-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
address-calculation 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
adjacency-list 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 adjacency-matrix and adjacency-list 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 adjacency-list representation is more compact for a sparse matrix.
Authors: BB,PEB
adjacency-matrix 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 adjacency-matrix and adjacency-list 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 adjacency-list 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 45-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
adversary
(definition)
Definition:
A theoretical agent that uses information about the past moves of an on-line algorithm to choose inputs that force the worst-case cost of the algorithm.
Note:
From Algorithms and Theory of Computation Handbook, page 10-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
Aho-Corasick
(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):333-340, 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, on-line algorithm, off-line algorithm, oblivious algorithm, external memory algorithm, heuristic.
Note:
The word comes from the Persian author Abu Ja'far Mohammed ibn Mûsâ al-Khowâ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):163-180, 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 depth-first 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 7-3, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 24-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 98-108, and D. Kozen, On Parallelism in Turing Machines, pages 89-97, both in Proc. Seventeenth Annual IEEE Symposium on Foundations of Computer Science, 1976.
American flag sort
(algorithm)
Definition:
An efficient, in-place 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):5-27, 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):306-318, 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 20-14 and 20-25, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
antichain
(definition)
Definition:
A subset of mutually incomparable elements in a poset.
Note:
From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 well-defined sense called the performance guarantee.
Note:
From Algorithms and Theory of Computation Handbook, page 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
arborescence
(definition)
Definition:
Informally, a directed tree.
Note: Arborescence
Author: PEB
arithmetic coding
(algorithm)
Definition:
A minimal variable-length message coding based on the frequency of each character. The message is represented by a fraction which is the repeated offset-plus-product reduction of the range (offset) and probability (product) of each character.
Note:
Shannon-Fano is a minimal prefix code. Huffman is optimal for character coding (one character-one 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):520-540, 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 vi, we could add the following rule for get.
- get(i, new()) = vi
Typically arrays have a fixed size and use either 0-based indexing or one-based indexing. Fixed initial size and 0-based 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
One-based 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, one-based indexing, 0-based indexing.
Note: An unordered array must be searched with
a linear search. Average search time may be improved
using a move-to-front 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.)
one-based indexing, 0-based 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 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 big-O notation.
Note:
From Algorithms and Theory of Computation Handbook, page 19-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 big-O notation.
Note:
From Algorithms and Theory of Computation Handbook, page 19-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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 7-3, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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
average-case 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 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
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. Look-up, insertion, and deletion are O(log n), where n is the number of nodes in the tree.
Generalization (I am a kind of ...)
height-balanced tree, balanced binary tree, binary search tree, red-black 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, Adelson-Velskii 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 red-black tree.
Author: PEB
More information
explanation and example.
Georgii M. Adelson-Velskii and Evgenii M. Landis, An algorithm for the organization of information, Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259-1263, 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
|
