﻿ Algorithms and Data Structures Glossary (Starting with "A")    Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators  #### Algorithms and Data Structures Glossary(Starting with "A")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

### 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
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.

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.

1. new() returns a stack
2. popOff(push(v, S)) = S
3. 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.

1. isEmpty(new()) = true
2. 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

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

(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

C. Levcopoulos and O. Petersson, Adaptive Heapsort, J. of Algorithms 14:395-413, 1993.

(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

Explanation of algorithm FGK and Vitter's Algorithm (algorithm V), two different adaptive Huffman coding algorithms.

(data structure)

Definition: A tree for multidimensional points where successive levels may be split along different dimensions.

Note: After [GG98].

Author: PEB

(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

(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

(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

(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

(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

(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

(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

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

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 ...)

Author: PEB

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

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

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

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

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.

1. new() returns an array
2. get(i, set(i, v, A)) = v
3. 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.

1. 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.

1. new(s) returns an array, which has a size s
2. size(new(s)) = s
3. size(set(i, v, A)) = size(A)
4. get(i, set(i, v, A)) = v if 0 ≤ i < size(A)
5. 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

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

#### 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

#### 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

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.

#### 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.

1. new() returns a stack
2. popOff(push(v, S)) = S
3. 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

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Published - April 2009

Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

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

 Use More Glossaries Use Free Dictionaries Use Free Translators Submit Your Glossary Read Translation Articles Register Translation Agency Submit Your Resume Obtain Translation Jobs Subscribe to Free Newsletter Buy Database of Translators Obtain Blacklisted Agencies Vote in Polls for Translators Read News for Translators Advertise Here Read our FAQ Read Testimonials Use Site Map       