Algorithms and Data Structures Glossary
(Starting with "B")

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

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

B_k tree

blind sort

blind trie

block

block addressing index

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

Bradford's law

branch and bound

breadth-first search

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

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

8. isEmpty(new()) = true
9. isEmpty(add(v, B)) = false

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 |T_l|, divided by the total number of leaves of the tree. Formally, ρ(T) = |T_l|/|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.

Author: ASK

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.

Author: ASK

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.

Author: ASK

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".
Called an "admissible tree" by Adelson-Velskii and Landis.

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.

Author: ASK

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.

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.

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 log₁₀ ( 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 log₁₀ ( 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).

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(n²) 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.

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((log₂ u v)²) bit operations.

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.

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.

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.

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.

     mid = (high + low)/2; 

     mid = low + (high - low)/2; 

Author: PEB

binary search tree

(data structure)

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.

Also known as dyadic 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.
(Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)

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 {n₁,..., n_k} be nodes of the multiway tree, T. Let {n'₁,..., n'_k} be nodes of the corresponding binary tree B. Node n_k corresponds to n'_k. In particular, nodes n_k and n'_k have the same labels and if n_k is the root of T, n'_k is the root of B. Connections correspond as follows:

• If n_l is the leftmost child of n_k, n'_l is the left child of n'_k. (If n_k has no children, n'_k has no left child.)
• If n_s is the next (immediately right) sibling of n_k, 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.

                  1           
                 /|\          
                / | \         
               /  |  \        
              2   3   4       
             / \      |       
            5   6     7       
                     / \      
                    8   9     
 

                  1           
                 /            
                /             
               /              
              2---3---4       
             /       /        
            5---6   7         
                   /          
                  8---9       
 

                1             
               /              
              2               
             / \              
            5   3             
             \   \            
              6   4           
                 /            
                7             
               /              
              8               
               \              
                9             
 

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.

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 2^k 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 B_k, whose root has k children where the i^th child is binomial tree of order k-i.

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.

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 e_i and e_j, the locus of points equidistant from e_i and e_j. That is {p|d(p,e_i)=d(p(e_j)}, where d is some distance metric.

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.

     compareAndSwap(0, 1);
     compareAndSwap(2, 3);
     compareAndSwap(0, 2);
     compareAndSwap(1, 3);
     compareAndSwap(1, 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

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

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: (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

block addressing index

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

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.

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 2ⁿ 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

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

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.

Author: PEB

Scott Aaronson's Complexity Zoo

Bradford's law

(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².

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.

Author: PEB

A more formal and complete explanation.

breadth-first search

(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 ...)
exhaustive search, breadth-first search.

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.

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

See links at B-tree.

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.

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.

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.

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.

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?

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.

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

Free Newsletter

Menu

Advertisements