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

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

### B

backtracking
bag
balance
balanced binary search tree
balanced binary tree
balanced k-way merge sort
balanced merge sort
balanced multiway merge
balanced multiway tree: see B-tree
balanced quicksort
balanced tree
balanced two-way merge sort
BANG file
Batcher sort: see bitonic sort
Baum Welch algorithm
BB(α) tree
BBP algorithm
BDD
BD-tree
Bellman-Ford algorithm
Benford's law
best case
best-case cost
best-first search
biconnected component
biconnected graph
bidirectional bubble sort
big-O notation
binary function
binary GCD
binary heap
binary insertion sort
binary knapsack problem: see knapsack problem
binary priority queue
binary relation
binary search
binary search tree
binary tree
binary tree representation of trees
bingo sort
binomial heap
binomial tree
bin packing problem
bin sort: see bucket sort
bintree
bipartite graph
bipartite matching
bisector
bitonic sort
bit vector
Bk tree
blind sort
blind trie
block
blocking flow
block search: see jump search
Bloom filter
blossom
bogosort
boolean
boolean expression
boolean function
border
Boruvka's algorithm
bottleneck traveling salesman
bottom-up tree automaton
boundary-based representation
bounded error probability in polynomial time: see BPP
bounded queue
bounded stack
Boyer-Moore
Boyer-Moore-Horspool
bozo sort
B+-tree
BPP
branch and bound
Bresenham's algorithm
brick sort
bridge
British Museum technique
brute force
brute force string search
brute force string search with mismatches
BSP-tree
B*-tree
B-tree
bubble sort
bucket
bucket array
bucketing method
bucket sort
bucket trie
buddy system
buddy tree
build-heap
Burrows-Wheeler transform
busy beaver
BV-tree
BWT: see Burrows-Wheeler transform
Byzantine generals

#### backtracking

(algorithmic technique)

Definition: Find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points and alternate choices using recursion.

Note: Conceptually, a backtracking algorithm does a depth-first search of a tree of possible (partial) solutions. Each choice is a node in the tree.

Author: PEB

Explanation with the 8-queens problems. maze solving Java applet. James D. Allen's short explanation.

An early exposition of this technique:
Solomon W. Golomb and Leonard D. Baumert, Backtrack Programming, Journal of ACM, 12(4):516-524, Oct 1965.
"This rather universal method was named 'backtrack' by Professor D. H. Lehmer of the University of California at Berkeley."

#### bag

(data structure)

Definition: An unordered collection of values that may have duplicates.

Formal Definition: A bag has a single query function, numberIn(v, B), which tells how many copies of an element are in the bag, and two modifier functions, add(v, B) and remove(v, B). These may be defined with axiomatic semantics as follows.

1. new() returns a bag
2. numberIn(v, new()) = 0
3. numberIn(v, add(v, B)) = 1 + numberIn(v, B)
4. numberIn(v, add(u, B)) = numberIn(v, B) if v ≠ u
5. remove(v, new()) = new()
6. remove(v, add(v, B)) = B
7. remove(v, add(u, B)) = add(u, remove(v, B)) if v ≠ u
where B is a bag and u and v are elements.

The predicate isEmpty(B) may be defined with the following additional axioms.

1. isEmpty(new()) = true

Also known as multi-set.

Generalization (I am a kind of ...)
abstract data type.

Note: A bag, or multi-set, is a set where values may be repeated. Inserting 2, 1, 2 into an empty set gives the set {1, 2}. Inserting those values into an empty bag gives {1, 2, 2}. From another point of view, a set is unordered, too, but has each value at most once.

Author: PEB

#### balance

(definition)

Definition: The (weight) balance of a tree is the number of leaves of the left subtree of a tree, denoted |Tl|, divided by the total number of leaves of the tree. Formally, ρ(T) = |Tl|/|T|.

Also known as root balance.

Note: The balance of a node is the balance of the (sub)tree rooted at that node. After Johann Blieberger <blieb@auto.tuwien.ac.at>, Discrete Loops and Worst Case Performance, page 22.

Author: PEB

#### balanced binary search tree

(data structure)

Definition: A binary search tree that is balanced.

Generalization (I am a kind of ...)
balanced binary tree, binary search tree.

Note: Usually "balanced" means "height balanced".
Quentin F. Stout and Bette L. Warren,, Tree Rebalancing in Optimal Time and Space, CACM, 29(9):902-908, September 1986.

Author: PEB

Example of balancing a BST.

[Knuth98, 3:459, Sect. 6.2.3]
Knuth refers to "balanced trees", but defines them as ordered, for searching, and binary.

#### balanced binary tree

(data structure)

Definition: A binary tree where no leaf is more than a certain amount farther from the root than any other. After inserting or deleting a node, the tree may rebalanced with "rotations."

Generalization (I am a kind of ...)
binary tree.

Specialization (... is a kind of me.)
AVL tree, red-black tree, B-tree, balanced binary search tree.

Aggregate child (... is a part of or used in me.)
left rotation, right rotation.

Author: PEB

AVL tree explanation and example

#### balanced k-way merge sort

(algorithm)

Definition: A merge sort that sorts a data stream using repeated merges. It distributes the input into k streams by repeatedly reading a block of input that fits in memory, called a run, sorting it, then writing it to the next stream. It then repeatedly merges the k streams and puts each merged run into one of j output streams until there is a single sorted output.

Note: This is an external sort.

#### balanced merge sort

(algorithm)

Definition: A k-way merge sort in which the number of input and output data streams is the same. See balanced k-way merge sort.

Note: This is an external sort.

#### balanced quicksort

(algorithm)

Definition: A variant of quicksort which attempts to choose a pivot likely to represent the middle of the values to be sorted.

Note: This is one of several attempts to prevent bad worst cases in quicksort by choosing the initial pivot.

#### balanced tree

(data structure)

Definition: A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced.

Generalization (I am a kind of ...)
tree.

Specialization (... is a kind of me.)
BB(α) tree, height-balanced tree, B-tree, AVL tree, full binary tree, red-black tree.

Note: Usually "balanced" means "height balanced".

Author: PEB

[Knuth98, 3:459, Sect. 6.2.3]

#### balanced two-way merge sort

(algorithm)

Definition: A balanced k-way merge sort that sorts a data stream using repeated merges. It distributes the input into two streams by repeatedly reading a block of input that fits in memory, a run, sorting it, then writing it to the next stream. It then repeatedly merges the two streams and puts each merged run into one of two output streams until there is a single sorted output.

Generalization (I am a kind of ...)
external sort.

#### BANG file

(data structure)

Definition: A balanced and nested grid (BANG) file is a point access method which divides space into a nonperiodic grid. Each spatial dimension is divided by a linear hash. Cells may intersect, and points may be distributed between them.

Note: After [GG98].

Author: PEB

#### Baum Welch algorithm

(algorithm)

Definition: An algorithm to find hidden Markov model parameters A, B, and Π with the maximum likelihood of generating the given symbol sequence in the observation vector.

Aggregate child (... is a part of or used in me.)
hidden Markov model.

Note: Contributed by Arvind <uk_arvind@mail.utexas.edu> May 2002.

Author: PEB

#### BB(α) tree

(data structure)

Definition: A binary tree where the balance of every subtree, ρ(T'), is bounded by α ≤ ρ(T') ≤ 1-α.

Also known as weight-balanced tree.

Generalization (I am a kind of ...)
binary tree, balanced tree.

Specialization (... is a kind of me.)
D-tree.

Note: After Johann Blieberger <blieb@auto.tuwien.ac.at>, Discrete Loops and Worst Case Performance, page 22.

See [GBY91, pages 100-102].

Author: PEB

#### BBP algorithm

(algorithm)

Definition: Compute the nth hexadecimal digit of π efficiently, without having to compute preceding digits.

Author: PEB

David Bailey, Peter Borwein, and Simon Plouffe, On the rapid computation of various polylogarithmic constants, Math. Comp. 66(1997), 903-913.

#### BDD

(data structure)

Definition: A binary lattice data structure that succinctly represents a truth table by collapsing redundant nodes and eliminating unnecessary nodes.

Note: A short bibliography of Binary Decision Diagrams. Randy Bryant's homepage

A BDD is a full binary tree.

Author: PEB

Starting with slide 39, Monica Lam shows how a BDD relates to a truth table in Software Design Rules.

Randy E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35(8):677-691, August, 1986.

#### BD-tree

(data structure)

Definition: A binary tree that organizes multidimensional points by splitting off regular subintervals.

Generalization (I am a kind of ...)
binary tree, point access method.

Note: After [GG98].

Author: PEB

Yutaka Ohsawa and Masao Sakauchi, BD-Tree: A New N-dimensional Data Structure with Efficient Dynamic Characteristics, Proc. 9th World Computer Congress, IFIP83, pp. 539-544, 1983.

"Bounded deformation" trees for collision resolution are described in
Doug L. James and Dinesh K. Pai, BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models, ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004.

#### Bellman-Ford algorithm

(algorithm)

Definition: An efficient algorithm to solve the single-source shortest-path problem. Weights may be negative. The algorithm initializes the distance to the source vertex to 0 and all other vertices to ∞. It then does V-1 passes (V is the number of vertices) over all edges relaxing, or updating, the distance to the destination of each edge. Finally it checks each edge again to detect negative weight cycles, in which case it returns false. The time complexity is O(VE), where E is the number of edges.

Also known as Ford-Bellman.

Aggregate parent (I am a part of or used in ...)
Johnson's algorithm.

Note: After [CLR90, page 532]

Author: PEB

#### Benford's law

(definition)

Definition: On a wide variety of statistical data, the first digit is d with the probability log10 ( 1 + 1/d ).

Note: This is also referred to as "the first-digit phenomenon." The general significant-digit law is that the first significant digits ddd... d occur with the probability log10 ( 1 + 1/ddd... d ). This law was first published by Simon Newcomb in 1881. It went unnoticed until Frank Benford, apparently unaware of Newcomb's paper, concluded the same law and published it in 1938, supported by huge amounts of data.

Author: PEB

#### best case

(definition)

Definition: (1) The situation or input for which an algorithm or data structure takes the least time or resources. (2) Having to do with this situation or input.

Author: PEB

#### best-case cost

(definition)

Definition: The minimum cost to process an input sequence.

Also known as optimal cost.

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

#### best-first search

(algorithm)

Definition: A state-space search algorithm that considers the estimated best partial solution next. This is typically implemented with a priority queue.

Note: This can be seen as an improved breadth-first search. Since there are different ways to compute the "estimated best", there are variants of best-first search: uniform-cost search (estimated best is the least cost so far), greedy search (least estimated cost to goal), A* (cost so far plus estimated cost to goal), and many refinements of those.

Author: PEB

Wikipedia entry for A* search.

#### biconnected component

(definition)

Definition: A maximal subset of edges of a connected graph such that the corresponding induced subgraph cannot be disconnected by deleting any vertex.

Note: That is, the subgraph is biconnected or has no cut vertex. From Algorithms and Theory of Computation Handbook, page 6-6, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### biconnected graph

(definition)

Definition: A connected graph that is not broken into disconnected pieces by deleting any single vertex (and incident edges).

Note: Informally, there are at least two independent paths from any vertex to any other vertex.

After Algorithms and Theory of Computation Handbook, page 6-6, Copyright © 1999 by CRC Press LLC.

Author: PEB

#### bidirectional bubble sort

(algorithm)

Definition: A variant of bubble sort that compares each adjacent pair of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning. It stops when a pass does no swaps.

Also known as cocktail shaker sort, shaker sort, double-direction bubble sort.

Generalization (I am a kind of ...)
sort.

Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.

Authors: PEB, BB

#### big-O notation

(definition)

Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n. Also known as O.

See also Ω(n), ω(n), Θ(n), , little-o notation, asymptotic upper bound, asymptotically tight bound, NP, complexity, model of computation.

Note: As an example, n² + 3n + 4 is O(n²), since n² + 3n + 4 < 2n² for all n > 10. Strictly speaking, 3n + 4 is O(n²), too, but big-O notation is often misused to mean equal to rather than less than. The notion of "equal to" is expressed by Θ(n).

The importance of this measure can be seen in trying to decide whether an algorithm is adequate, but may just need a better implementation, or the algorithm will always be too slow on a big enough input. For instance, quicksort, which is O(n log n) on average, running on a small desktop computer can beat bubble sort, which is O(n²), running on a supercomputer if there are a lot of numbers to sort. To sort 1,000,000 numbers, the quicksort takes 20,000,000 steps on average, while the bubble sort takes 1,000,000,000,000 steps! See Jon Bentley, Programming Pearls: Algorithm Design Techniques, CACM, 27(9):868, September 1984 for an example of a microcomputer running BASIC beating a supercomputer running FORTRAN.

Any measure of execution must implicitly or explicitly refer to some computation model. Usually this is some notion of the limiting factor. For one problem or machine, the number of floating point multiplications may be the limiting factor, while for another, it may be the number of messages passed across a network. Other measures which may be important are compares, item moves, disk accesses, memory used, or elapsed ("wall clock") time.

[Knuth97, 1:107], [HS83, page 31], and [Stand98, page 466] use |f(n)| ≤ c|g(n)|. In computational complexity theory "only positive functions are considered, so the absolute value bars may be left out." (Wikipedia, "Big O notation"). This definition after [CLR90, page 26].

Strictly, the character is the upper-case Greek letter Omicron, not the letter O, but who can tell the difference?

Author: PEB

Wikipedia Big O notation. Big O is a Landau Symbol.

Donald E. Knuth, Big Omicron and Big Omega and Big Theta, SIGACT News, 8(2):18-24, April-June 1976.

#### binary function

(definition)

Definition: A function with two arguments.

Author: PEB

#### binary GCD

(algorithm)

Definition: Compute the greatest common divisor of two integers, u and v, expressed in binary. The run time complexity is O((log2 u v)²) bit operations.

Note: Discovered by J. Stein in 1967. Another source says discovered by R. Silver and J. Tersian in 1962 and published by G. Stein in 1967.

The algorithm uses the following observations.

• If u and v are both even, gcd(u,v) = 2 gcd(u/2, v/2).
• If u is even and v is odd, gcd(u,v) = gcd(u/2, v).
• Otherwise both are odd, and gcd(u,v) = gcd(|u-v|/2, v). (Euclid's algorithm with a division by 2 since the difference of two odd numbers is even.)

Here is the algorithm. It is especially efficient for operations on binary representations.

1. g = 1
2. while u is even and v is even
• u = u/2 (right shift)
• v = v/2
• g = 2*g (left shift)
now u or v (or both) are odd
3. while u > 0
• if u is even, u = u/2
• else if v is even, v = v/2
• else
• t = |u-v|/2
• if u < v, then v = t else u = t
4. return v*g

Algorithm B in [Knuth97, vol. 2, Sect. 4.5.2]. Torsten Eichstädt suggested incrementing g in step 2.3 (g++) and returning v left shifted g times in step 4 (return v<<g). 4 April 2006. Alex Peyser pointed out that g must start at 0. 10 July 2008.

Author: PEB

Euclid's Algorithm including examples and references.

#### binary heap

(data structure)

Definition: A complete binary tree where every node has a key more extreme (greater or less) than or equal to the key of its parent.

Generalization (I am a kind of ...)
complete binary tree, heap, k-ary heap with k=2.

Specialization (... is a kind of me.)
treap.

Aggregate parent (I am a part of or used in ...)
build-heap, heapify, heapsort, priority queue.

Aggregate child (... is a part of or used in me.)
array.

Note: Insertion is O(log2 n) where n is the number of nodes. A binary heap can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with one-based indexing. If a child index is greater than the number of nodes, the child does not exist.

Merging two binary heaps is O(n): the best you can do is just concatenate two heap arrays and make a heap of the result. Two binomial heaps can be merged in O(ln n). Two Fibonacci heaps can be merged in Θ(1).

Author: CLK

#### binary insertion sort

(algorithm)

Definition:Insertion sort in which the proper location for the next item is found with a binary search.

Generalization (I am a kind of ...)
insertion sort.

Author: PEB

#### binary priority queue

(data structure)

Definition: A priority queue implemented with a binary tree having the following restrictions:

• The key of a node is greater than keys of its children, i.e., it has the heap property.
• If the right subtree is not empty, the left subtree is not empty.
• If there are both left and right children, the left child's key is greater than the right child's key.

Generalization (I am a kind of ...)
priority queue.

Aggregate child (... is a part of or used in me.)
binary tree, heap property.

Note: The subtree restriction means that when inserting at a leaf, the left subtree is always used before the right subtree. Favoring the left subtree tends to make the tree taller and thinner.

After [GBY91, pages 223-225].

Author: PEB

#### binary relation

(definition)

Definition: A relation between exactly two items at a time, such as "greater than" (>), "not equal to" (≠), "proper subset of" (⊂), or "is connected to" (has an edge to) for vertices of a graph.

Generalization (I am a kind of ...)
relation.

Specialization (... is a kind of me.)
dictionary.

Note: One may think of a binary relation as a binary function whose range is {true, false}. For example since 3 > 2, GreaterThan(3, 2) = true.

Author: PEB

#### binary search

(algorithm)

Definition: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Generalization (I am a kind of ...)
dichotomic search.

Aggregate parent (I am a part of or used in ...)
binary insertion sort, ideal merge, suffix array.

Aggregate child (... is a part of or used in me.)
divide and conquer.

Note: Run time is O(ln n).

Finding the middle is often coded as

`     mid = (high + low)/2; `
This overflows if high and low are close to the largest expressible integer. The following gives the same result and never overflows, if high and low are non-negative.
`     mid = low + (high - low)/2; `
Thanks to Colin D. Wright, 1 June 2005.

The implementation of search in C uses 0-based indexing.

Author: PEB

#### binary search tree

(data structure)

Definition: A binary tree where every node's left subtree has keys less than the node's key, and every right subtree has keys greater than the node's key.

Generalization (I am a kind of ...)
binary tree, search tree.

Specialization (... is a kind of me.)
AVL tree, splay tree, threaded tree, randomized binary search tree, discrete interval encoding tree.

Aggregate parent (I am a part of or used in ...)
treesort (1).

Note: A binary search tree is almost always implemented with pointers, but may have a variety of constraints on how it is composed.

Author: PEB

A animation (Java).

#### binary tree

(data structure)

Definition: A tree with at most two children for each node.

Formal Definition: A binary tree either

• is empty (no nodes), or
• has a root node, a left binary tree, and a right binary tree.

Generalization (I am a kind of ...)
tree, k-ary tree with k=2.

Specialization (... is a kind of me.)
complete binary tree, full binary tree, binary search tree, binary heap, balanced binary tree, threaded tree, Fibonacci tree, extended binary tree.

Note: Formal definition after [CLR90, page 94].

Author: PEB

Historical Note
An early use of the term "dyadic tree" is in 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.

#### binary tree representation of trees

(data structure)

Definition: A way to represent a multiway tree as a binary tree. The leftmost child, c, of a node, n, in the multiway tree is the left child, c', of the corresponding node, n', in the binary tree. The immediately right sibling of c is the right child of c'.

Formal Definition: A multiway tree T can be represented by a corresponding binary tree B. Let {n1,..., nk} be nodes of the multiway tree, T. Let {n'1,..., n'k} be nodes of the corresponding binary tree B. Node nk corresponds to n'k. In particular, nodes nk and n'k have the same labels and if nk is the root of T, n'k is the root of B. Connections correspond as follows:

• If nl is the leftmost child of nk, n'l is the left child of n'k. (If nk has no children, n'k has no left child.)
• If ns is the next (immediately right) sibling of nk, n's is the right child of n'k.

Also known as first child-next sibling binary tree, doubly-chained tree, filial-heir chain.

Aggregate parent (I am a part of or used in ...)
multiway tree, k-ary tree, Schorr-Waite graph marking algorithm.

Note: See [Knuth97, 1:333, Sect. 2.3.2].

The binary tree representation of a multiway tree or k-ary tree is based on first child-next sibling representation of the tree. In this representation every node is linked with its leftmost child and its next (right nearest) sibling.

Let us see one example. Consider the following multiway tree

`                  1                            /|\                          / | \                        /  |  \                      2   3   4                    / \      |                   5   6     7                            / \                          8   9      `
This tree can be represented in first child-next sibling manner as follows
`                  1                            /                            /                            /                            2---3---4                    /       /                    5---6   7                            /                            8---9        `
Now, if we look at the first child-next sibling representation of the tree closely, we will see that it forms a binary tree. To see this better, we can rotate every next-sibling edge 45 degrees clockwise. After that we get the following binary tree:
`                1                            /                            2                            / \                          5   3                          \   \                          6   4                            /                            7                            /                            8                              \                              9              `
This is binary tree representation of the given (multiway) tree.

Authors: AL,PEB

#### bingo sort

(algorithm)

Definition: A variant of selection sort that orders items by first finding the least value, then repeatedly moving all items with that value to their final location and find the least value for the next pass. This is more efficient than selection sort if there are many duplicate values.

Generalization (I am a kind of ...)
selection sort.

Note: To see why it is more efficient, consider one value. Selection sort does one pass through remaining items for each item moved. Bingo sort does one pass for each value (not item) and moves every item with that value to its final location.

The name refers to the exclamation, Bingo!, when an item with the right value is found.

The best case complexity is Θ(n+m²), where n is the number of items and m is the number of unique values. The worst case complexity, which is the same as the average case complexity, is Θ(nm).

Author: PEB

Kenneth A. Berman and Jerome L. Paul, Fundamentals of Sequential and Parallel Algorithms, Sect. 4.6, pages 137-139, PWS Publishing Co., Boston, MA, 1996.

#### binomial heap

(data structure)

Definition: A heap made of a forest of binomial trees with the heap property numbered k=0, 1, 2, ..., n, each containing either 0 or 2k nodes. Each tree is formed by linking two of its predecessors, by joining one at the root of the other. The operations of insert a value, decrease a value, delete a value, and merge or join (meld) two queues take O(log n) time. The find minimum operation is a constant Θ(1).

Generalization (I am a kind of ...)
heap.

Aggregate parent (I am a part of or used in ...)
priority queue, Dijkstra's algorithm.

Aggregate child (... is a part of or used in me.)
binomial tree.

Note: Binomial heaps are so called because the number of nodes at each level of each subtree is a binomial coefficient. Sometimes called a binomial queue. After LK.

Author: PEB

#### binomial tree

(data structure)

Definition: An ordered tree of order k ≥ 0, that is Bk, whose root has k children where the ith child is binomial tree of order k-i.

Note: A Bk tree has 2k nodes, the height is k, and there are k choose i nodes at depth i.

Adapted from [CLR90, pages 401 and 402]. CLR90 numbers the children k-1, k-2, ..., 0, making child i a binomial tree of order i. This definition numbers the children from 1 to k.

Author: PEB

Binomial heap in Wikipedia.

#### bin packing problem

(classic problem)

Definition: Determine how to put the most objects in the least number of fixed space bins. More formally, find a partition and assignment of a set of objects such that a constraint is satisfied or an objective function is minimized (or maximized). There are many variants, such as, 3D, 2D, linear, pack by volume, pack by weight, minimize volume, maximize value, fixed shape objects, etc.

Note: A common form of the problem is, what is the least number of bins (containers of fixed volume) needed to hold a set of objects. This problem often appears in manufacturing. For instance, suppose we need a number of pipes of different, specific lengths to plumb a house and we can buy pipe stock in 5 meter lengths. How can we cut the 5 meter pipes to waste as little as possible (minimize the cost of pipe)?

Author: PEB

Limits and references. Suggestions on books and related topics.

#### bintree

(data structure)

Definition: A regular decomposition k-d tree for region data.

Note: From Algorithms and Theory of Computation Handbook, page 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### bipartite graph

(definition)

Definition: An undirected graph where vertices can be partitioned into two sets such that no edge connects vertices in the same set.

Generalization (I am a kind of ...)
layered graph.

Note: A bipartite graph is a layered graph with two layers.

Author: PEB

#### bipartite matching

(definition)

Definition: (1) A perfect matching between vertices of a bipartite graph, that is, a subgraph which pairs every vertex with exactly one other vertex. (2) The problem of finding such a matching.

Also known as maximum bipartite matching.

Author: PEB

#### bisector

(definition)

Definition: For two elements ei and ej, the locus of points equidistant from ei and ej. That is {p|d(p,ei)=d(p(ej)}, where d is some distance metric.

Note: For instance, if ei and ej are two points in the plane and we use Euclidean distance, the bisector is the perpendicular bisector of the line segment ei,ej.

From Algorithms and Theory of Computation Handbook, page 20-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

#### bitonic sort

(algorithm)

Definition: Compare, and swap if necessary, pairs of elements in parallel. Subsets are sorted then merged.

Also known as Batcher sort.

Generalization (I am a kind of ...)
oblivious algorithm.

Note: This takes O((log n)2/2) stages (or steps) with n/2 comparators at each stage.

This sorts increasingly larger intermingled subsets, somewhat like Shell sort, and merges subsets, like merge sort.

Elements are compared and swapped in a fixed (oblivious) schedule, so this may be implemented with only conditional swaps. Here is a Batcher sort for four elements:

`     compareAndSwap(0, 1);     compareAndSwap(2, 3);     compareAndSwap(0, 2);     compareAndSwap(1, 3);     compareAndSwap(1, 2); `
where compareAndSwap(i,j) is if (a[i] < a[j]) Swap(a[i], a[j]).

This is Knuth's Algorithm M [Knuth98, 3:111, Sect. 5.2.2].

Author: PEB

K. E. Batcher, Sorting Networks and their Applications, Proc. AFIPS Spring Joint Computer Conference, 32:307-314, 1968.

#### bit vector

(data structure)

Definition: An array of bits.

Note: A bit vector can often be handled very efficiently since a computer word is an array of bits.

Author: PEB

#### Bk tree

(data structure)

Definition: A binomial tree of order (height) k.

Author: PEB

#### blind sort

(algorithm)

Definition: A specialized sort algorithm that first builds a blind trie, then traverse the tree left to right.

Generalization (I am a kind of ...)
sort.

Aggregate parent (I am a part of or used in ...)
suffix array.

Aggregate child (... is a part of or used in me.)
blind trie, depth-first search.

Note: Used in a specialized algorithm to build suffix arrays.

Author: PEB

Paolo Ferragina and Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM, 46(2):236 - 280, March 1999.

#### blind trie

(data structure)

Definition: A specialized Patricia tree whose internal nodes store only an integer, k, which is the length of the common prefix of the strings in the children. Equivalently, the strings first differ in the (k+1)st character.

Generalization (I am a kind of ...)
Patricia tree.

Aggregate parent (I am a part of or used in ...)
blind sort.

Note: Used in a specialized algorithm, described in Engineering a Lightweight Suffix Array Construction Algorithm, to build suffix arrays.

The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.

Author: PEB

Defined in the following, but called a Patricia tree
Paolo Ferragina and Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM, 46(2): 236 - 280, (March 1999).

Called "blind trie" in
Giovanni Manzini and Paolo Ferragina, Engineering a Lightweight Suffix Array Construction Algorithm, Algorithmica, 40(1):33-50, (Jun 2004).

#### block

(definition)

Definition: (1) A number of items which are handled together for efficiency. (2) A sequence of don't care symbols.

Note: (2) 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.

Authors: PEB,CRC-A

(data structure)

Definition: An inverted index that includes the block, or general location, within texts, in addition to the text in which the word appears.

Generalization (I am a kind of ...)
inverted index.

Note: See the example at inverted index.

Author: PEB

Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro, and Ricardo Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems, IEEE Computer, 33(11):37-44, November 2000, (page 42).

#### blocking flow

(definition)

Definition: A flow function in which any directed path from the source to the sink contains a saturated edge.

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

#### Bloom filter

(algorithm)

Definition: A probabilistic algorithm to quickly test membership in a large set using multiple hash functions into a single array of bits.

Aggregate parent (I am a part of or used in ...)

Note: This involves a particular data structure, the bit array, too. A Bloom filter is good for secret sharing: giving a Bloom filter lets someone see if you have an item (it is found in the Bloom filter), but it is impractical to recreate the whole collection.

Author: PEB

Wikipedia entry, which gives many variants and extensions. Trade-offs and engineering techniques with links to sites with recent papers, hash functions, etc. Another explanation typo: probability of false positive is missing a minus sign; exponent should be ... e-kn/m. Using Bloom filters. Language is Perl.

Burton Bloom, Space/time trade-offs in hash coding with allowable errors, CACM, 13(7):422-426, July 1970.

#### blossom

(definition)

Definition: An odd length cycle which appears during a matching algorithm on general graphs.

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

#### bogosort

(algorithm)

Definition: A terribly inefficient sort algorithm that repeatedly generates a random permutation of the items until the items are in order.

Generalization (I am a kind of ...)
Las Vegas algorithm.

Note: From the slang "bogus" meaning "bad" as in "I can't believe anybody would be so thoughtless to write/do/say/believe that, and I just can't let it pass without objecting."

Fastest run time is Θ(n). Average run time is Ω(n × n!). From
Hermann Gruber, Markus Holzer, and Oliver Ruepp, Sorting the slow way: An analysis of perversely awful randomized sorting algorithms, FUN 2007, LNCS 4475, pp. 183-197, 2007. Available at http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf
Note: the permutation subroutine given for Algorithm 1 is Fisher-Yates shuffle. Also "Supercalifragilisticexpialidocious" is misspelled on the sixth page, although it is spelled correctly in the footnote.

Author: PEB

#### boolean

(definition)

Definition: (1) In computer science, entities having just two values: 1 or 0, true or false, on or off, etc. along with the operations and, or, and not. (2) In mathematics, entities from an algebra equivalent to intersection, union, and complement over subsets of a given set.

Note: A mathematical boolean algebra based on a set of size n has 2n values. The operations, intersection and union (or and and or), are commutative and associative, and each distributes over the other. Each operation has an identity, and complement produces the inverse. Binary logic is the boolean algebra which two values.

Author: PEB

#### boolean expression

(definition)

Definition: An expression consisting solely of boolean variables and values and boolean operations, such as and, or, not, implies, etc.

Author: PEB

#### boolean function

(definition)

Definition: A function whose range is {0, 1}. It can be understood to evaluate the truth or falsity of each element of its domain.

Author: SKS

#### border

(definition)

Definition: A string v which is both a prefix and a suffix of another string u. String v is the border of u if it is the longest proper border of u.

Note: From Algorithms and Theory of Computation Handbook, page 11-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

#### Boruvka's algorithm

(algorithm)

Definition: Compute a minimum spanning tree.

Author: PEB

Eppstein's lecture outlining and contrasting MST algorithms.

O. Boruvka, O jistem problemu minimalnim, Praca Moravske Prirodovedecke Spolecnosti, 3:37-58, 1926. (in Czech) (The u in Boruvka has a small o above it.)

#### bottleneck traveling salesman

(classic problem)

Definition: Find a tour where no edge is more costly than some (bottleneck) amount.

Note: Defined in comp.theory by Hai Zhou (haizhou@cs.utexas.edu) November 1998. See [CLR90, page 974].

Author: PEB

#### boundary-based representation

(definition)

Definition: A representation of a region that is based on its boundary.

Note: From Algorithms and Theory of Computation Handbook, page 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### bounded queue

(data structure)

Definition: A queue limited to a fixed number of items.

Author: PEB

#### bounded stack

(data structure)

Definition: A stack limited to a fixed number of items.

Author: PEB

#### Boyer-Moore

(algorithm)

Definition: A string matching algorithm that compares characters from the end of the pattern to its beginning. When characters don't match, searching jumps to the next possible match: the farthest of a table like that used in the Knuth-Morris-Pratt algorithm and the next matching position in the pattern.

Generalization (I am a kind of ...)
string matching.

Note: After [Sund98].

Author: PEB

Series of pages explaining how Boyer-Moore works.

Robert S. Boyer and J Strother Moore, A Fast String Search Algorithm, CACM, 20(10):762-772, October 1977.

#### Boyer-Moore-Horspool

(algorithm)

Definition: A string matching algorithm that compares characters from the end of the pattern to its beginning. When characters don't match, searching jumps to the next matching position in the pattern.

Also known as Horspool.

Author: PEB

R. Nigel Horspool, Practical Fast Searching in Strings, Software - Practice and Experience, 10:501-506, 1980.

#### bozo sort

(algorithm)

Definition: A terribly inefficient sort algorithm that randomly swaps items until they are in order.

Generalization (I am a kind of ...)
Las Vegas algorithm.

Note: Run time analysis in
Hermann Gruber, Markus Holzer, and Oliver Ruepp, Sorting the slow way: An analysis of perversely awful randomized sorting algorithms, FUN 2007, LNCS 4475, pp. 183-197, 2007. Available at http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf
Note: "Supercalifragilisticexpialidocious" is misspelled on the sixth page, although it is spelled correctly in the footnote.

Author: PEB

#### B+-tree

(data structure)

Definition: A B-tree in which keys are stored in the leaves.

Generalization (I am a kind of ...)
B-tree.

Note: An early use of the name, "B+-tree", is Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, 11(2):121-137, June 1979.

Author: PEB

#### BPP

(definition)

Definition: The class of languages for which a membership computation by a probabilistic Turing machine halts in polynomial time with the right answer (accept or reject) at least 2/3 of the time. "BPP" means "Bounded error Probability in Polynomial" time.

Also known as bounded error probability in polynomial time.

Note: By repeating the run, the chance of error may be arbitrarily reduced.

After [Hirv01, page 19].

Author: PEB

Scott Aaronson's Complexity Zoo

(definition)

Definition: Journals in a field can be divided into three parts, each with about one-third of all articles: 1) a core of a few journals, 2) a second zone, with more journals, and 3) a third zone, with the bulk of journals. The number of journals is 1:n:n².

Note: Bradford formulated his law after studying a bibliography of geophysics, covering 326 journals in the field. He discovered that 9 journals contained 429 articles, 59 contained 499 articles, and 258 contained 404 articles. Although Bradford's Law is not statistically accurate, librarians commonly use it as a guideline.

Contributed by Arvind <uk_arvind@mail.utexas.edu> May 2002.

Author: PEB

#### branch and bound

(algorithmic technique)

Definition: An algorithmic technique to find the optimal solution by keeping the best solution found so far. If a partial solution cannot improve on the best, it is abandoned.

Note: For instance, suppose we want to find the shortest route from Zarahemla to Manti, and at some time the shortest route found until that time is 387 kilometers. Suppose we are to next consider routes through Cumeni. If the shortest distance from Zarahemla to Cumeni is 350 km and Cumeni is 46 km from Manti in a straight line, there is no reason to explore possible roads from Cumeni: they will be at least 396 km (350 + 46), which is worse than the shortest known route. So we need not explore paths from Cumeni.

This may be implemented as a backtracking algorithm, which is a modified depth-first search, or using a priority queue ordering partial solutions by lower bounds (current + least possible completion), which is a best-first search.

This technique is not helpful if all solutions are about the same or the initial solutions are very poor and better solutions are only found gradually. In either case, the cost is similar to exploring the entire solution space.

Author: PEB

A more formal and complete explanation.

(algorithm)

Definition: Any search algorithm that considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. This is typically implemented with a queue.

Note: In a tree, called a level-order traversal.

Author: PEB

Lecture notes from Design and Analysis of Algorithms on Breadth-first search and depth-first search. A animation (Java).

#### Bresenham's algorithm

(algorithm)

Definition: An efficient algorithm to render a line with pixels. The long dimension is incremented for each pixel, and the fractional slope is accumulated.

Note: Bresenham discusses implementation issues and design choices, such as arise drawing lines beginning at either end point of a line or approximating a circle with a polygon, in
Jack Bresenham, Ambiguities in incremental line rastering, IEEE Computer Graphics and Applications, 7(5):31-43, May, 1987.

Author: PEB

An explanation.

Eugen Dedu's implementation of a Bresenham-based supercover line algorithm. It marks all the squares a line passes through, not just the least error squares. It may help with dithered lines or checking for obstacles.

Jack E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1):25-30, 1965.
Reprinted in Interactive Computer Graphics, Herbert Freeman ed., 1980, and Seminal Graphics: Pioneering Efforts That Shaped The Field, Rosalee Wolfe ed., ACM SIGGRAPH, 1998.

Historical Note
In November 2001 Jack E. Bresenham wrote, "I was working in the computation lab at IBM's San Jose development lab. A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console. [The algorithm] was in production use by summer 1962, possibly a month or so earlier. Programs in those days were freely exchanged among corporations so Calcomp (Jim Newland and Calvin Hefte) had copies. When I returned to Stanford in Fall 1962, I put a copy in the Stanford comp center library.

A description of the line drawing routine was accepted for presentation at the 1963 ACM national convention in Denver, Colorado. It was a year in which no proceedings were published, only the agenda of speakers and topics in an issue of Communications of the ACM. A person from the IBM Systems Journal asked me after I made my presentation if they could publish the paper. I happily agreed, and they printed it in 1965."

#### bridge

(definition)

Definition: An edge of a connected graph whose removal would make the graph unconnected.

Author: PEB

#### British Museum technique

(algorithmic technique)

Definition: Find a solution by checking all possibilities one by one, beginning with the smallest. This is a conceptual, not a practical, technique where the number of possibilities are enormous.

Generalization (I am a kind of ...)

Note: For instance, one may, in theory, find the smallest program that solves a particular problem in the following way: Generate all possible source codes of length one character. Check each one to see if it solves the problems. (Note: the halting problem makes this check troublesome.) If not, generate and check all programs of two characters, three characters, etc. Conceptually this finds the smallest program, but in practice it takes far more time than the age of the universe.

Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. is possible or impossible.

Author: PEB

#### brute force

(algorithmic technique)

Definition: An algorithm that inefficiently solves a problem, often by trying every one of a wide range of possible solutions.

Specialization (... is a kind of me.)
exhaustive search, brute force string search.

Note: After LK.

Author: PEB

#### brute force string search

(algorithm)

Definition: An algorithm to find a string within another string or body of text by trying each position one at a time. There are many far faster string matching algorithms.

Also known as naive string search.

Author: PEB

#### brute force string search with mismatches

(algorithm)

Definition: Beginning with the (leftmost) position in a string and trying each position in turn, find the number of characters for which the pattern and the substring beginning at that position don't match (the Hamming distance). Return the first position with k or fewer mismatches.

Generalization (I am a kind of ...)
string matching with mismatches, brute force string search.

Author: PEB

#### BSP-tree

(data structure)

Definition: A binary space partitioning (BSP) tree is a binary tree for multidimensional points where successive levels are split by arbitrary hyperplanes.

Note: After [GG98].

Author: PEB

#### B*-tree

(data structure)

Definition: A B-tree in which nodes are kept 2/3 full by redistributing keys to fill two child nodes, then splitting them into three nodes.

Author: PEB

#### B-tree

(data structure)

Definition: A balanced search tree in which every node has between m/2 and m children, where m>1 is a fixed integer. m is the order. The root may have as few as 2 children. This is a good structure if much of the tree is in slow memory (disk), since the height, and hence the number of accesses, can be kept small, say one or two, by picking a large m.

Also known as balanced multiway tree.

Generalization (I am a kind of ...)
balanced tree, search tree.

Specialization (... is a kind of me.)
2-3-4 tree, B*-tree, 2-3 tree.

Note: The origin of "B-tree" has never been explained by the authors. ... "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. [Bayer and McCreight were at Boeing Scientific Research Labs in 1972.] Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees.     -
Douglas Comer
, The Ubiquitous B-Tree, Computing Surveys, 11(2):123, June 1979.

After [HS83, page 499].

Author: PEB

A tutorial on the basics, and variants.

Rudolf Bayer and Edward M. McCreight, Organization and Maintenance of Large Ordered Indices, Acta Informatica, 1:173-189, 1972.

#### bubble sort

(algorithm)

Definition: Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.

Also known as sinking sort, exchange sort.

Generalization (I am a kind of ...)
in-place sort, stable sort.

Note: Complexity is O(n2) for arbitrary data, but approaches Θ(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better since at least one item is moved forward or backward to its place in the list with each pass. Gnome sort optimizes the moving forward and backward instead of blindly looping through all items.

Since at least one item is moved into its final place for each pass, an improvement is to decrement the last position checked on each pass.

The name "sinking sort" comes from elements sinking down to their proper position. Contributed by Ken Tata (Ken.Tata@onsemi.com) 22 December 2000. After LK.

Author: PEB

animation of many sorting algorithms; animation (Java).

Marvin V. Zelkowitz, Principles of Software Engineering and Design, Prentice-Hall, page 107, 1979.

#### bucket

(definition)

Definition: An area of storage where items with a common property are stored. Typically tree data structures and sort algorithms use many buckets, one for each group of items. Usually buckets are kept on disk.

Generalization (I am a kind of ...)
bag.

Aggregate parent (I am a part of or used in ...)
radix sort, bucket sort, elastic-bucket trie, hash heap, extendible hashing.

Note: A bucket is used when a number of items need to be kept together, but the order among them is not important. Conceptually it is a bag (rather than a set).

Author: PEB

#### bucket array

(data structure)

Definition: Implementation of a dictionary by an array indexed by the keys of the items in the dictionary.

Note: From Algorithms and Theory of Computation Handbook, page 4-28, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### bucketing method

(definition)

Definition: Data organization methods that decompose the space from which spatial data is drawn into regions called buckets. Some conditions for the choice of region boundaries include the number of objects that they contain or on their spatial layout (e.g. minimizing overlap or coverage).

Note: From Algorithms and Theory of Computation Handbook, page 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### bucket sort

(algorithm)

Definition: A distribution sort where input elements are initially distributed to several buckets based on an interpolation of the element's key. Each bucket is sorted if necessary, and the buckets' contents are concatenated.

Also known as bin sort.

Generalization (I am a kind of ...)
distribution sort.

Specialization (... is a kind of me.)
histogram sort, counting sort, top-down radix sort, postman's sort, distributive partitioning sort.

Note: A bucket sort uses fixed-size buckets (or a list per bucket). A histogram sort sets up buckets of exactly the right size in a first pass. A counting sort uses one bucket per key.

The space required is one bucket for every few possible key value, but is O(n log log n) taking into account a distribution of keys. That is, some buckets will have a lot of keys.

Bucket sorts work well for data sets where the possible key values are known and relatively small and there are on average just a few elements per bucket. This means the cost of sorting the contents of each bucket can be reduced toward zero. The ideal result is if the order in each bucket is uninteresting or trivial, for instance, when each bucket holds a single key. The buckets may be arranged so the concatenation phase is not needed, for instance, the buckets are contiguous parts of an array.

Bucket sorts can be stable.

Author: PEB

#### bucket trie

(data structure)

Definition: A variant of a trie in which leaf nodes are buckets which hold up to k strings. Usually implies fixed sized buckets.

Generalization (I am a kind of ...)
trie.

Specialization (... is a kind of me.)
elastic-bucket trie.

Note: Combining terminal strings can greatly shorten branches. For instance, "extraordinarily", "extraordinariness", and "extraordinary" can be stored in one bucket at the end of a short branch distinguishing them from extran... and extrap... rather than a long branch for the common substring ...ordinar...

The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.

Author: PEB

Edward H. Sussenguth, Jr., Use of Tree Structures for Processing Files, CACM, 6(5):272-279, May 1963.

#### buddy system

(algorithm)

Definition: A memory allocation strategy which recursively divides allocatable blocks of memory into pairs of adjacent equal-sized blocks called "buddies."

Note: This is included to minimize confusion with a buddy tree. After LK.

Author: PEB

#### buddy tree

(data structure)

Definition: A point access method which splits multidimensional space in different dimensions at each level. It also keeps a minimum bounding box of points accessible by each node.

Note: After [GG98].

Author: PEB

Bernhard Seeger and Hans-Peter Kriegel, The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems, 16th International Conference on Very Large Data Bases (VLDB), pages 590-601, 1990.

#### build-heap

(algorithm)

Definition: Convert an array into a heap by executing heapify progressively closer to the root. For an array of n nodes, this takes O(n) time under the comparison model.

Aggregate parent (I am a part of or used in ...)
heapsort, JSort.

Aggregate child (... is a part of or used in me.)
heapify.

Note: After [CLR90, page 145].

Author: PEB

#### Burrows-Wheeler transform

(algorithm)

Definition: Rearrange a string so repeated substrings lead to repeated characters in the rearranged string, which is easier to compress. Knowing which character was last in the original string, the original can be reconstructed from the rearranged string.

Also known as BWT.

Aggregate child (... is a part of or used in me.)
sort.

Author: PEB

Wikipedia entry for Burrows-Wheeler transform.

Michael Burrows and David J. Wheeler, A Block-sorting Lossless Data Compression Algorithm, Research Report SRC-124, Digital Equipment Corporation, Palo Alto, California, May 1994.
This transform is algorithm C in the paper.

#### busy beaver

(classic problem)

Definition: (1) A Turing machine with a small number of states that halts when started with a blank tape, but writes a huge number of non-blanks or takes a huge number of steps. (2) The problem of finding the maximum number of non-blanks written or steps taken for any Turing machines with a given number of states and symbols.

Note: The problem is well-defined but rapidly becomes impractical to determine for even a small number of states and symbols. This problem is related to the halting problem since one must determine if a machine is looping or eventually halts.

Author: PEB

History, explanation, and links about the Busy Beaver Turing Machine. Heiner Marxen's currently known busy beaver results page.

#### BV-tree

(data structure)

Definition: A conceptual idea which generalizes B-trees to multiple dimensions. BV-trees are not balanced, and searching may require backtracking.

Note: After [GG98].

Author: PEB

#### Byzantine generals

(classic problem)

Definition: The problem of reaching a consensus among distributed units if some of them give misleading answers. To be memorable, the problem is couched in terms of generals deciding on a common plan of attack. Some traitorous generals may lie about whether they will support a particular plan and what other generals told them. Exchanging only messages, what decision making algorithm should the generals use to reach a consensus? What percentage of liars can the algorithm tolerate and still correctly determine a consensus?

Note: The 1975 paper is the first published consideration of the problem of consensus in the presence of faults that I know of, but the 1982 paper names the problem.

One variant is: suppose two separated generals will win if both attack at the same time and lose if either attacks alone, but messengers may be captured. If one decides to attack, how can that general be sure that the message has reached the other general and the other general will attack, too?

Author: PEB

Summary of the 1982 paper by Lamport, Shostak, and Pease.

E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber, Some constraints and tradeoffs in the design of network communications, Proc. 5th ACM Symposium on Operating Systems Principles, pages 67-74, 1975.
Marshall Pease, Robert Shostak, and Leslie Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM 27(2):228-234, 1980.
Leslie Lamport, Robert Shostak and Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.
Both available in PDF.

 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       