Algorithms and Data Structures Glossary (Starting with "D")
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
$8 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
D
 Dadjacent
 DAG: see directed acyclic graph
 DAG shortest paths
 data structure
 DAWG: see directed acyclic word graph
 decidable language
 decidable problem
 decimation: see prune and search
 decision problem
 decomposable searching problem
 degree
 dense graph
 depoissonization
 depth
 depthfirst search
 deque
 derangement
 descendant
 deterministic
 deterministic algorithm
 deterministic finite automata string search
 deterministic finite automaton: see deterministic finite state machine
 deterministic finite state machine
 deterministic finite tree automaton
 deterministic pushdown automaton
 deterministic tree automaton
 DeutschJozsa algorithm
 DFA: see deterministic finite state machine
 DFS: see depthfirst search
 DFS forest
 DFTA: see deterministic finite tree automaton
 diagonalization
 diameter
 dichotomic search
 dictionary
 diet: see discrete interval encoding tree
 difference
 digital search tree
 digital tree
 digraph: see directed graph
 Dijkstra's algorithm
 diminishing increment sort
 dining philosophers
 direct chaining
 directed acyclic graph
 directed acyclic word graph
 directed graph
 discrete interval encoding tree
 discrete pcenter
 disjoint set
 disjunction
 distributional complexity
 distribution sort
 distributive partitioning sort
 divide and conquer
 divide and marriage before conquest
 division method
 domain
 dominance tree sort
 don't care
 Doomsday rule
 doubledirection bubble sort: see bidirectional bubble sort
 doubleended priority queue
 double hashing
 double left rotation
 double metaphone
 double right rotation
 doublychained tree: see binary tree representation of trees
 doublyended queue: see deque
 doubly linked list
 DPDA: see deterministic pushdown automaton
 Dtree
 dual
 dual linear program
 Dutch national flag
 dyadic tree: see binary tree
 dynamic
 dynamic array
 dynamic hashing
 dynamic Huffman coding: see adaptive Huffman coding
 dynamic programming
 dynamization transformation
Dadjacent
(definition)
Definition:
An entry reachable for a (d1)extremal entry through a unit vertical, horizontal, or diagonalmismatch step.
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
DAG shortest paths
(algorithm)
Definition:
Solve the singlesource shortestpath problem in a weighted directed acyclic graph by 1) doing a topological sort on the vertices by edge so vertices with no incoming edges are first and vertices with only incoming edges are last, 2) assign an infinite distance to every vertex (dist(v)=∞) and a zero distance to the source, and 3) for each vertex v in sorted order, for each outgoing edge e(v,u), if dist(v) + weight(e) < dist(u), set dist(u)=dist(v) + weight(e) and the predecessor of u to v.
Author: PEB
data structure
(definition)
Definition:
An organization of information, usually in memory, for better algorithm efficiency, such as queue, stack, linked list, heap, dictionary, and tree, or conceptual unity, such as the name and address of a person. It may include redundant information, such as length of the list or number of nodes in a subtree.
Specialization (... is a kind of me.)
external memory data structure, passive data structure, active data structure, persistent data structure, recursive data structure.
Note:
Most data structures have associated algorithms to perform operations, such as search, insert, or balance, that maintain the properties of the data structure.
Author: PEB
decidable language
(definition)
Definition:
A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps  equivalently, can be recognized by a Turing machine that halts for all inputs.
Also known as recursive language, totally decidable language.
Note:
For emphasis, the equivalent term totally decidable language is sometimes used. From Algorithms and Theory of Computation Handbook, page 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
decidable problem
(definition)
Definition:
A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps. The associated language is called a decidable language.
Also known as totally decidable problem, algorithmically solvable, recursively solvable.
Note:
For emphasis, the equivalent term totally decidable problem is sometimes used. From Algorithms and Theory of Computation Handbook, pages 2419 and 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
decision problem
(definition)
Definition:
A problem with a "yes" or "no" answer. Equivalently, a function whose range is two values, such as {0,1}.
Note:
A decision problem asks, is there a solution with a certain characteristic? An optimization problem asks, what is the best solution? For instance, the traveling salesman problem is an optimization problem, while the corresponding decision problem asks if there is a Hamiltonian cycle with a cost less than some fixed amount k.
From Algorithms and Theory of Computation Handbook, page 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
More information
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP.
decomposable searching problem
(definition)
Definition:
A searching problem for which one can decompose the searched domain into subsets, find answers from these subsets, and combine these answers to form the solution to the original problem. More formally a problem with a query Q is decomposable given if there exists an efficiently computable associative and commutative binary operator @ satisfying the condition: Q(x, A ∪ B) = @(Q(x,A),Q(x,B)).
Note:
From Algorithms and Theory of Computation Handbook, page 2026, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
degree
(definition)
Definition:
(1) Of a vertex, the number of edges connected to it. (2) Of a graph, the maximum degree of any vertex. (3) Of a tree node, the number of child nodes it has.
Note:
From Algorithms and Theory of Computation Handbook, page 621, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
dense graph
(definition)
Definition:
A graph in which the number of edges is close to the possible number of edges.
Generalization (I am a kind of ...)
graph.
Specialization (... is a kind of me.)
complete graph.
Note:
A directed graph can have at most n(n1) edges, where n is the number of vertices. An undirected graph can have at most n(n1)/2 edges.
There is no strict distinction between sparse and dense graphs. Bruno Preiss' definition of sparse and dense graphs has problems, but may help. First, for one graph, one can always choose a k. Second a class of graphs might be considered sparse if E = O(V^{k}) and 2 > k > 1. E is the number of edges, and V is the number of vertices.
Preiss reference from Andreas Leiser <andreas.leiser@bluewin.ch> 22 December 2003
Author: PEB
depoissonization
(definition)
Definition:
To interpret a solution to a poisson model in the original model after poissonization.
Note:
From Algorithms and Theory of Computation Handbook, page 1435, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
depth
(definition)
Definition:
Of a node, the distance from the node to the root of the tree.
Aggregate parent (I am a part of or used in ...)
tree.
Note:
For instance, the root is at depth 0, and a child of the root is at depth 1.
Author: PEB
depthfirst search
(algorithm)
Definition:
(1) Any search algorithm that considers outgoing edges (children) of a vertex before any of the vertex's siblings, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first. This is easily implemented with recursion. (2) An algorithm that marks all vertices in a directed graph in the order they are discovered and finished, partitioning the graph into a forest.
Also known as DFS.
Specialization (... is a kind of me.)
preorder traversal, inorder traversal, postorder traversal.
Note:
Depthfirst search doesn't specify if a vertex is considered before, during, or after its outgoing edges or children. Thus it can be preorder, inorder, or postorder traversal.
[CLR90, pages 477485]
Author: PEB
More information
Lecture notes from Design and Analysis of Algorithms on Breadthfirst search and depthfirst search. An animation (Java).
An early mention of depthfirst search: C. Cordell Green and Bertram Raphael, The use of theoremproving techniques in questionanswering systems, Proc. 1968 23rd ACM national conference, pages 169181, 1968. Uses just "depthfirst search" in the body (page 5), but contrasts depthfirst with breadthfirst search in a footnote.
An earlier description of what we would call depthfirst search with pruning of infeasible solutions. Solomon W. Golomb and Leonard D. Baumert, Backtrack Programming, Journal of ACM, 12(4):516524, Oct 1965.
deque
(data structure)
Definition:
A data structure in which items may be added to or deleted from the head or the tail.
Also known as doublyended queue.
Note:
Short for DoubleEnded QUEue. Pronounced "deck". After [Knuth97, vol 1, page 239].
Author: PEB
derangement
(algorithm)
Definition:
A permutation of elements, where no element is in its original position.
Author: PEB
More information
The (Combinatorial) Object Server's information on Derangements
descendant
(definition)
Definition:
A child of a node in a tree, any of the children of the children, etc.
Note:
of a tree node
Author: PEB
deterministic
(definition)
Definition:
Permitting at most one next move at any step in a computation.
Note:
From Algorithms and Theory of Computation Handbook, pages 2419 and 1521, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
deterministic algorithm
(algorithmic technique)
Definition:
An algorithm whose behavior can be completely predicted from the input.
Note:
That is, each time a certain set of input is presented, the algorithm does the same computations and gives the same results as any other time the set of input is presented. For algorithms with state, or that maintain information between inputs, "the input" means everything since the algorithm was started from an initial state. There can be degrees of deterministic behavior. For instance, an algorithm that uses random numbers is not usually considered deterministic. However if the "random numbers" come from a pseudorandom number generator, the behavior may be deterministic.
Author: PEB
deterministic finite automata string search
(algorithm)
Definition:
A string matching algorithm which builds a deterministic finite state machine to recognize the search string. The machine is then run at each location in turn. If the machine accepts, that is a match.
Author: PEB
deterministic finite state machine
(definition)
Definition:
A finite state machine with at most one transition for each symbol and state.
Also known as DFA, deterministic finite automaton.
Note:
Some fields, like model checking, require (and assume) that there is exactly one transition for each symbol and state. A machine that has at least one transition for each symbol and state is sometimes called "complete".
Author: PEB
deterministic finite tree automaton
(definition)
Definition:
A deterministic finite state machine that accepts finitary trees rather than just strings. The tree nodes are marked with the letters of the alphabet of the automaton, and the transition function encodes the next states for each branch of the tree. The acceptance condition is modified accordingly.
Also known as DFTA.
Author: SKS
More information
Tree Automata Techniques and Applications page.
deterministic tree automaton
(definition)
Definition:
A deterministic finite state machine that accepts infinite trees rather than just strings. The tree nodes are marked with the letters of the alphabet of the automaton, and the transition function encodes the next states for each branch of the tree. The expressive power of such automata varies depending on the acceptance conditions of the trees.
Note:
These are used in various studies in branchingtime temporal logic, second order logic with multiple successors, etc.
Author: SKS
More information
Tree Automata Techniques and Applications page.
DeutschJozsa algorithm
(algorithm)
Definition:
A quantum algorithm to determine whether a function is constant or balanced, that is, returns 1 for half the domain and 0 for the other half. For a function taking n input qubits, first, do Hadamards on n 0's, forming all possible inputs, and a single 1, which will be the answer qubit. Next, run the function once; this exclusive or's the result with the answer qubit. Finally, do Hadamards on the n inputs again, and measure the answer qubit. If it is 0, the function is constant, otherwise the function is balanced.
Note:
The algorithm needs only one (quantum) evaluation of the function. A classical algorithm to answer the same question is to examine one more than half the domain in the worst case. See Arthur O. Pittenger, "An Introduction to Quantum Computing Algorithms", page 41, or Michael A. Nielsen and Isaac L. Chuang, "Quantum Computation and Quantum Information", pages 3436.
Author: PEB
DFS forest
(definition)
Definition:
A rooted forest formed by depthfirst search.
Note:
From Algorithms and Theory of Computation Handbook, page 621, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
diagonalization
(definition)
Definition:
A proof technique for showing that a given language does not belong to a given complexity class, used in many separation theorems.
Note:
From Algorithms and Theory of Computation Handbook, page 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
diameter
(definition)
Definition:
The maximum of the distances between all possible pairs of vertices of a graph.
Note:
The distance between two vertices u and v in a weighted graph is the sum of weights of the edges of a shortest path between them. For unweighted graph, it is the number of edges of a shortest path.
From Algorithms and Theory of Computation Handbook, page 2026, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
dichotomic search
(definition)
Definition:
Search by selecting between two distinct alternatives (dichotomies) at each step.
Note:
Division into multiple alternatives is polychotomy.
Author: PEB
dictionary
(data structure)
Definition:
An abstract data type storing items, or values. A value is accessed by an associated key. Basic operations are new, insert, find and delete.
Formal Definition: The operations new(), insert(k, v, D), and find(k, D) may be defined with axiomatic semantics as follows.
 new() returns a dictionary
 find(k, insert(k, v, D)) = v
 find(k, insert(j, v, D)) = find(k, D) if k ≠ j
where k and j are keys, v is a value, and D is a dictionary. The modifier function delete(k, D) may be defined as follows.  delete(k, new()) = new()
 delete(k, insert(k, v, D)) = delete(k, D)
 delete(k, insert(j, v, D)) = insert(j, v, delete(k, D)) if k ≠ j
If we want find to be a total function, we could define find(k, new()) using a special value: fail. This only changes the return type of find.
 find(k, new()) = fail
Also known as association list, map, property list.
Generalization (I am a kind of ...)
binary relation, abstract data type.
Specialization (... is a kind of me.)
associative array.
Note:
The terms "association list" and "property list" are used with LISPlike languages and in the area of Artificial Intelligence. These suggest a relatively small number of items, whereas a dictionary may be quite large. Professionals in the Data Management area have specialized semantics for "dictionary" and related terms. A dictionary defines a binary relation that maps keys to values. The keys of a dictionary are a set.
Contributions by Rob Stewart 16 March 2004.
Author: PEB
difference
(definition)
Definition:
The difference of set A minus set B is a set having all the members which are in A, but not in B.
Note:
For example, {2, 3, 5}  {7, 5} = {2, 3}.
Author: PEB
digital search tree
(data structure)
Definition:
A trie which stores the strings in internal nodes, so there is no need for extra leaf nodes to store the strings.
Author: PEB
digital tree
(data structure)
Definition:
A tree for storing strings in which nodes are organized by substrings common to two or more strings.
Generalization (I am a kind of ...)
tree.
Specialization (... is a kind of me.)
digital search tree, trie, Patricia tree, suffix tree.
Author: PEB
Dijkstra's algorithm
(algorithm)
Definition:
An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. All weights must be nonnegative.
Aggregate parent (I am a part of or used in ...)
Johnson's algorithm.
Aggregate child (... is a part of or used in me.)
priority queue, greedy algorithm.
Note:
A naive implementation of the priority queue gives a run time complexity O(V²), where V is the number of vertices. Implementing the priority queue with a Fibonacci heap makes the time complexity O(E + V log V), where E is the number of edges. After [CLR90, page 527].
Author: PEB
diminishing increment sort
(algorithm)
Definition:
An inplace sort algorithm that repeatedly reorders different, small subsets of the input until the entire array is ordered. On each pass it handles i sets of n/i items, where n is the total number of items. Each set is every i^{th} item, e.g. set 1 is item 1, 1+i, 1+2i, etc., set 2 is item 2, 2+i, etc. On each succeeding pass, the increment or gap, i, is reduced until it is 1 for the last pass.
Generalization (I am a kind of ...)
inplace sort.
Specialization (... is a kind of me.)
Shell sort, comb sort.
Note:
Since items may move large distances at first, this method is quite efficient. Comb sort does a single "bubbling" pass (ala bubble sort) over each set for each gap or increment, whereas Shell sort completely sorts each set.
Shell had the first increment be half the number of items to be sorted, i.e., n/2, and each succeeding increment half the preceding increment. This lowers efficiency since the same items are compared over and over. Relatively prime increments are better. Since one of the sets can be visualized as those items where the teeth of a comb touch, this is sometimes called a comb sort. Using this analogy, the teeth get closer on each pass. However, the term "comb sort" is used for a specific algorithm. Knuth uses "diminishing increment sort" as a synonym of "Shell sort", but we include comb sort.
Authors: PEB,ASK
dining philosophers
(classic problem)
Definition:
Suppose a number of philosophers surround a dining table. Adjacent philosophers share one fork. They spend time thinking or trying to eat. A philosopher must have both the fork on the left and the fork on the right to eat. Clearly adjacent philosophers cannot eat at the same time. The problem is to find an algorithm for taking forks that prevents deadlock, starvation, etc.
Author: PEB
direct chaining
(data structure)
Definition:
A collision resolution scheme in which the hash table is an array of links to lists. Each list holds all the items with the same hash value.
Generalization (I am a kind of ...)
separate chaining.
Aggregate parent (I am a part of or used in ...)
hash table.
Note:
The items in the list may be searched and maintained with any list search algorithms. Any searchable data structure may be used instead of a list. After [GBY91, pages 7174]
Author: PEB
directed acyclic graph
(definition)
Definition:
A directed graph with no path that starts and ends at the same vertex.
Also known as DAG, acyclic directed graph, oriented acyclic graph.
Generalization (I am a kind of ...)
directed graph, acyclic graph.
Author: PEB
directed acyclic word graph
(data structure)
Definition:
(1) A directed acyclic graph representing the suffixes of a given string in which each edge is labeled with a character. The characters along a path from the root to a node are the substring which the node represents. (2) A finite state machine that recognizes a set of words.
Also known as DAWG.
Note:
A variant, the compact DAWG, labels the edges with strings, not just single characters. In the compact DAWG, any node which is an only child is merged with its parent and the edge labels are concatenated. Another variant is the morphic DAWG, where some substrings are coded with new characters, like a simplified Huffman coding.
Author: PEB
More information
JohnPaul Adamovsky's Directed Acyclic Word Graph or DAWG page with introduction, explanation, C implementation, and notes on optimization.
(1) Andrew W. Appel and Guy J. Jacobson, The World's Fastest Scrabble Program, CACM, 31(5):572578, May 1988. Good description and comparison with a trie. M. Crochemore and R. Verin, Direct Construction of Compact Directed Acyclic Word Graphs, 8th Annual Symposium, CPM 97, Aarhus, Denmark, 116129, 1997. (2) J. Aoe, K. Morimoto, M. Shishibori and KH. Park, A Trie Compaction Algorithm for a Large Set of Keys, IEEE Trans. Knowledge and Data Engineering, 8(3):476491, 1996. D. Perrin, Finite Automata, in: J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Elsevier, Amsterdam, Vol. A, 357, 1990.
directed graph
(data structure)
Definition:
A graph whose edges are ordered pairs of vertices. That is, each edge can be followed from one vertex to another vertex.
Formal Definition: A graph G is a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u,v)  u, v ∈ V}. If the graph does not allow selfloops, adjacency is irreflexive, that is E ⊆ {(u,v)  u, v ∈ V ∧ u ≠ v}.
Also known as digraph, oriented graph.
Generalization (I am a kind of ...)
graph.
Specialization (... is a kind of me.)
directed acyclic graph, weighted, directed graph, strongly connected graph, arborescence.
Aggregate child (... is a part of or used in me.)
source, sink, indegree, outdegree.
Note:
In contrast, undirected graphs merely connect the vertices, without any consideration for direction. For example, a map of streets in a neighborhood is an undirected graph, but a map that shows the postman's route through that neighborhood is a directed graph. A directed graph may be thought of as a neighborhood of oneway streets: the map must show the allowed direction of travel on each street. A regular twoway street may be thought of as two oneway streets.
Author: PEB
More information
Historical Note
John N. Warfield <Jnwarfield@aol.com> provides the following history of digraphs. In the HarvardOxford books on Aristotle, one of the translators suggests that Aristotle actually used something akin to digraphs in his teachings, but this was pure speculation. Augustus De Morgan invented the Theory of Relations and published the key work in 1847the same year in which Boole published his key book in which he credited De Morgan for essentially teaching Boole about logic. Since the Theory of Relations offers essentially the algebraic form of the digraph, it is unlikely that there was any formal use before 1847. Charles Sanders Peirce made clear the use of structural patterns in doing basic work, but his own graphics were not very useful in extended form, though some modern enthusiasts have extolled his "existential graphs".
The earliest actual drawing of a digraph as connected to De Morgan that I have been able to find occurs in the 1919 book by Bertrand Russell titled "Introduction to Mathematical Philosophy". If you find an earlier digraph, please contact me, John N. Warfield.
discrete interval encoding tree
(data structure)
Definition:
A binary search tree that stores consecutive values as intervals.
Also known as diet.
Generalization (I am a kind of ...)
binary search tree.
Note:
Each node is an interval signifying consecutive values, instead of a single value. This saves space and time if there are many sets of consecutive values.
Author: PEB
More information
Discrete Interval Encoding Trees with links to implementations. Abstract and links to full text of Diets for Fat Sets from Journal of Functional Programming, Vol. 8, No. 6, 1998.
discrete pcenter
(classic problem)
Definition:
A facility location problem in which the supply points must be a subset of demand points.
Note:
Adapted from [AS98, page 428].
Author: PEB
disjoint set
(definition)
Definition:
A set whose members do not overlap, are not duplicated, etc.
Note:
For example, the set of intervals {[1,5], [4,7], [8,9]} is not disjoint since [1,5] overlaps [4,7].
Author: PEB
disjunction
(definition)
Definition:
The boolean "or" function.
Author: PEB
distributional complexity
(definition)
Definition:
The expected running time of the best possible deterministic algorithm over the worst possible probability distribution on the inputs.
Note:
From Algorithms and Theory of Computation Handbook, page 1521, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
distribution sort
(algorithm)
Definition:
Any sort algorithm where data is distributed from its input to multiple intermediate structures which are then gathered and placed on the output.
Generalization (I am a kind of ...)
sort.
Specialization (... is a kind of me.)
bucket sort, linear probing sort, shuffle sort, merge sort, radix sort, UnShuffle sort, restricted universe sort, strand sort, distributive partitioning sort.
Note:
Many distribution sorts are also merge sorts depending on how the distribution is performed.
Author: ASK
distributive partitioning sort
(algorithm)
Definition:
Step 1: find the median key. Step 2: distribute the n items into n/2 buckets linearly covering the interval from the minimum to the median and n/2 buckets linearly covering the interval from the median to the maximum. Step 3: compact the buckets, removing empty buckets. Recursively start again at step 1 for any bucket with multiple items. Linked lists are used to avoid moving items until a final phase and to avoid bucket overflows.
Generalization (I am a kind of ...)
bucket sort.
Aggregate child (... is a part of or used in me.)
select k^{th} element, linked list.
Note:
Shuffle sort estimates the distribution of the items to be sorted by examining the first n/8 items. Distributive partitioning sort estimates the distribution by approximating the median and linearly interpolating from the minimum to the median and from the median to the maximum. Histogram sort counts the number of items in each (fixed) interval. See the note at histogram sort on distributing according to a rank function R.
The implementation outline in the paper has a preparation step. The step finds the median and partitions around it, then sorts the lower half and the upper half with the defined algorithm.
Author: PEB
More information
Wlodzimierz Dobosiewicz, Sorting by Distributive Partitioning, Information Processing Letters, 7(1):17, January 1978.
divide and conquer
(algorithmic technique)
Definition:
Solve a problem, either directly because solving that instance is easy (typically, because the instance is small) or by dividing it into two or more smaller instances. Each of these smaller instances is recursively solved, and the solutions are combined to produce a solution for the original instance.
Specialization (... is a kind of me.)
easy split, hard merge, hard split, easy merge.
Aggregate parent (I am a part of or used in ...)
heapify, merge sort, quicksort, binary search.
Note:
The technique is named "divide and conquer" because a problem is conquered by dividing it into several smaller problems. This technique yields elegant, simple and quite often very efficient algorithms. Wellknown examples include heapify, merge sort, quicksort, Strassen's fast matrix multiplication, fast multiplication (in O(n log n log log n), see E. A. Karatsuba's Fast Algorithms), the Fast Fourier Transform (FFT), and binary search. (Why is binary search included? The dividing part picks which segment to search, and "the solutions are combined" trivially: take the answer from the segment searched. Segments not searched are "recursively solved" by the null operation: they are ignored.) A similar principle is at the heart of several important data structures such as binary search tree, multiway search trees, tries, skip lists, multidimensional search trees (kd trees, quadtrees), etc.
Here is the translation of "divide and conquer" in different languages:
French: diviser pour régner
German: teile und herrsche Latin: divide et impera Spanish: divide y vencerás
Authors: PEB,CM
More information
Three divide and conquer sorting algorithms, as a means of using parallelism.
divide and marriage before conquest
(algorithmic technique)
Definition:
A variant of divide and conquer in which subproblems created in the "divide" step are merged before the "conquer" step.
Note:
From Algorithms and Theory of Computation Handbook, page 1926, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
domain
(definition)
Definition:
(1) The inputs for which a function or relation is defined. For instance, 0 is not in the domain of reciprocal (1/x). (2) The possible values of a variable.
Author: PEB
don't care
(definition)
Definition:
A special symbol which matches any other symbol of a given alphabet.
Note:
From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Doomsday rule
(algorithm)
Definition:
An algorithm to find the day of the week for any date. It is simple enough to memorize and do mentally.
Note:
Invented sometime before January 1976 by John Horton Conway, the mathematician who also invented the computer Game of Life.
Author: PEB
More information
Explanation, examples, origin, and links; a summary of the International Standard Date and Time Notation ISO 8601.
doubleended priority queue
(data structure)
Definition:
A priority queue which simultaneously keeps track of the maximum and minimum keys, and supports operations efficiently on either extreme (minimum or maximum).
Note:
After LK.
Author: PEB
double hashing
(algorithm)
Definition:
A method of open addressing for a hash table in which a collision is resolved by searching the table for an empty place at intervals given by a different hash function, thus minimizing clustering.
Also known as rehashing.
Note:
Since a different hashing function is used to find a location in case of collision, colliding values should be spread out. In linear probing, primary clustering occurs when collisions fill up every space for long stretches. Even in quadratic probing, secondary clustering may develop since colliding values follow the same probe sequence.
Author: PEB
double metaphone
(algorithm)
Definition:
An algorithm to code English words (and foreign words often heard in the United States) phonetically by reducing them to 12 consonant sounds. This reduces matching problems from wrong spelling.
Generalization (I am a kind of ...)
phonetic coding algorithm.
Note:
This is an improved version of metaphone. It returns two keys if a word has two feasible pronunciations, such as a foreign word.
Author: PEB
More information
Lawrence Philips, The Double Metaphone Search Algorithm, C/C++ Users Journal, June 2000. http://www.ddj.com/cpp/184401251 accessed December 2007.
doubly linked list
(data structure)
Definition:
A variant of a linked list in which each item has a link to the previous item as well as the next. This allows easily accessing list items backward as well as forward and deleting any item in constant time.
Also known as twoway linked list, symmetrically linked list.
Note:
See [Stand98, p. 91].
Author: PEB
Dtree
(data structure)
Definition:
(1) A BB(α) tree where the weights are the number of searches down that path. (2) A heightbalanced binary tree that divides regions along their boundaries to serve as a spatial access method.
Generalization (I am a kind of ...)
(1) BB(α) tree (2) binary tree, spatial access method, heightbalanced tree.
Note:
(1) Short for "dynamic tree".
Author: PEB
More information
(1) Kurt Mehlhorn, Dynamic Binary Search, SIAM Journal on Computing, 8(2):175198, May 1979. Abstract, article, and references.
(2) Jianliang Xu, Baibua Zheng, WangChien Lee, and Dik Lun Lee, The Dtree: An Index Structure for Planar Point Queries in LocationBased Wireless Services, IEEE Transactions on Knowledge and Data Engineering, 16(12):1526 1542, December 2004.
dual
(definition)
Definition:
The dual of a planar graph, G, is a graph with a vertex for each region in G and an edge between vertices for each pair of adjacent regions. The new edge crosses the edge in G which is the boundary between the adjacent regions.
Generalization (I am a kind of ...)
planar graph.
Note:
The dual of a planar graph is also planar. The original graph is the dual of the dual. That is, they are duals of each other. In the accompanying figure, the black circles and solid lines are one planar graph. The white squares and dotted lines are another planar graph. Each is the dual of the other.
Author: PEB
More information
Herman Servatius' Selfdual maps, that is, planar graphs that are duals of themselves.
dual linear program
(definition)
Definition:
Every linear program has a corresponding linear program called the dual. It is max_{y}{b· y  A^{T}y ≤ c and y ≥ 0}. For any solution x to the original linear program and any solution y to the dual we have c · x ≥ (A^{T} y)^{T} x = y^{T}(Ax) ≥ y · b. For optimal x and y, equality holds. For a problem formulated as an integer linear program, a solution to the dual of a relaxation of the program can serve as witness.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Dutch national flag
(classic problem)
Definition:
Rearrange elements in an array into three groups: bottom, middle, and top.
One algorithm is to have the top group grow down from the top of the array, the bottom group grow up from the bottom, and keep the middle group just above the bottom. The algorithm stores the locations just below the top group, just above the bottom, and just above the middle in three indexes. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it. Update the appropriate index. Complexity is Θ(n) moves and examinations.
Generalization (I am a kind of ...)
partition.
Aggregate parent (I am a part of or used in ...)
multikey Quicksort.
Note:
Using this algorithm in quicksort to partition elements, with the middle group being elements equal to the pivot, lets quicksort avoid "resorting" elements that equal the pivot.
Author: PEB
More information
A detailed tutorial on the algorithm. The flag of the Netherlands or the Dutch national flag.
James R. Bitner, An Asymptotically Optimal Algorithm for the Dutch National Flag Problem, SIAM Journal on Computing, 11(2):243262, May 1982. Colin L. McMaster, An Analysis of Algorithms for the Dutch National Flag Problem, CACM, 21(10):842846, October 1978. E. W. Dijkstra, A Discipline of Programming, PrenticeHall, 1976.
Historical Note
Lloyd Allison reports that Dijkstra used this problem as an exercise in program derivation and program proof. Allison first heard about the problem at the Institute of Computer Science (ICS), London University, about 1973. The algorithm is named for the problem of ordering red, white, and blue marbles into the order of the Dutch national flag.
dynamic
(definition)
Definition:
When the problem domain may change, e.g., there may be insertions and deletions.
Note:
From Algorithms and Theory of Computation Handbook, page 2026, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
dynamic array
(data structure)
Definition:
An array whose size may change over time. Items are not only added or removed, but memory used changes, too.
Note:
For instance, REDIM in Visual Basic or malloc() in C. In some languages, such as Perl, all arrays are dynamic.
Author: PR
dynamic hashing
(data structure)
Definition:
A hash table that grows to handle more items. The associated hash function must change as the table grows. Some schemes may shrink the table to save space when items are deleted.
Generalization (I am a kind of ...)
hash table.
Specialization (... is a kind of me.)
extendible hashing, linear hashing, spiral storage.
Aggregate child (... is a part of or used in me.)
load factor.
Author: PEB
More information
R. J. Enbody and H. C. Du, Dynamic Hashing Schemes, ACM Computing Surveys, 20(2):85113, June 1998. Note: Figure 5b has errors: boxes should be labeled (top to bottom) A, D, B, and C. PerÅke Larson, Dynamic hashing, BIT 18(2):184201, 1978. PerÅke Larson, Dynamic Hash Tables, CACM 31(4):446457, April 1988. Martin Dietzfelbinger, Anna Karlin, Kurt Melhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, and Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM J. Comput., 23(4):738761, August 1994.
dynamic programming
(algorithmic technique)
Definition:
Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them.
Aggregate parent (I am a part of or used in ...)
SmithWaterman algorithm Solves these problems: matrixchain multiplication problem, longest common substring, longest common subsequence.
Note:
From Algorithms and Theory of Computation Handbook, page 126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
More information
Dan Hirschberg's example of using dynamic programming for matrix multiplication and longest common substring and subsequence, including pseudocode.
dynamization transformation
(algorithmic technique)
Definition:
A data structuring technique that can make a static data structure dynamic. In so doing, the performance of the dynamic structure will exhibit certain spacetime tradeoffs.
Note:
From Algorithms and Theory of Computation Handbook, page 2026, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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
