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

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

### D

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
depth-first 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
Deutsch-Jozsa algorithm
DFA: see deterministic finite state machine
DFS: see depth-first 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 p-center
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
double-direction bubble sort: see bidirectional bubble sort
double-ended priority queue
double hashing
double left rotation
double metaphone
double right rotation
doubly-chained tree: see binary tree representation of trees
doubly-ended queue: see deque
DPDA: see deterministic pushdown automaton
D-tree
dual
dual linear program
Dutch national flag
dynamic
dynamic array
dynamic hashing
dynamic Huffman coding: see adaptive Huffman coding
dynamic programming
dynamization transformation

(definition)

Definition: An entry reachable for a (d-1)-extremal entry through a unit vertical, horizontal, or diagonal-mismatch step.

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

Author: CRC-A

#### DAG shortest paths

(algorithm)

Definition: Solve the single-source shortest-path 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 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 24-19 and 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

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

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

#### 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(n-1) edges, where n is the number of vertices. An undirected graph can have at most n(n-1)/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 14-35, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

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

#### depth-first 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, in-order traversal, postorder traversal.

Note: Depth-first search doesn't specify if a vertex is considered before, during, or after its outgoing edges or children. Thus it can be preorder, in-order, or postorder traversal.

[CLR90, pages 477-485]

Author: PEB

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

An early mention of depth-first search:
C. Cordell Green and Bertram Raphael, The use of theorem-proving techniques in question-answering systems, Proc. 1968 23rd ACM national conference, pages 169-181, 1968.
Uses just "depth-first search" in the body (page 5), but contrasts depth-first with breadth-first search in a footnote.

An earlier description of what we would call depth-first search with pruning of infeasible solutions.
Solomon W. Golomb and Leonard D. Baumert, Backtrack Programming, Journal of ACM, 12(4):516-524, 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 doubly-ended queue.

Note: Short for Double-Ended 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

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 24-19 and 15-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

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

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 branching-time temporal logic, second order logic with multiple successors, etc.

Author: SKS

Tree Automata Techniques and Applications page.

#### Deutsch-Jozsa 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 34-36.

Author: PEB

#### DFS forest

(definition)

Definition: A rooted forest formed by depth-first search.

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

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

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

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

1. new() returns a dictionary
2. find(k, insert(k, v, D)) = v
3. 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.

1. delete(k, new()) = new()
2. delete(k, insert(k, v, D)) = delete(k, D)
3. 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.

1. 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 LISP-like 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 in-place 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 ith 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 ...)
in-place 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.

#### 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 71-74]

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

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):572-578, 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, 116-129, 1997.

(2) J. Aoe, K. Morimoto, M. Shishibori and K-H. Park, A Trie Compaction Algorithm for a Large Set of Keys, IEEE Trans. Knowledge and Data Engineering, 8(3):476-491, 1996.

D. Perrin, Finite Automata, in: J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Elsevier, Amsterdam, Vol. A, 3-57, 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 self-loops, 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, in-degree, out-degree.

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 one-way streets: the map must show the allowed direction of travel on each street. A regular two-way street may be thought of as two one-way streets.

Author: PEB

Historical Note
John N. Warfield <Jnwarfield@aol.com> provides the following history of digraphs.

In the Harvard-Oxford 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 1847---the 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".

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

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 p-center

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

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

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

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

Wlodzimierz Dobosiewicz, Sorting by Distributive Partitioning, Information Processing Letters, 7(1):1-7, 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. Well-known 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 (k-d 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

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 19-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

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

Explanation, examples, origin, and links; a summary of the International Standard Date and Time Notation ISO 8601.

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

Lawrence Philips, The Double Metaphone Search Algorithm, C/C++ Users Journal, June 2000. http://www.ddj.com/cpp/184401251 accessed December 2007.

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

Note: See [Stand98, p. 91].

Author: PEB

#### D-tree

(data structure)

Definition: (1) A BB(α) tree where the weights are the number of searches down that path. (2) A height-balanced 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, height-balanced tree.

Note: (1) Short for "dynamic tree".

Author: PEB

(1) Kurt Mehlhorn, Dynamic Binary Search, SIAM Journal on Computing, 8(2):175-198, May 1979. Abstract, article, and references.

(2) Jianliang Xu, Baibua Zheng, Wang-Chien Lee, and Dik Lun Lee, The D-tree: An Index Structure for Planar Point Queries in Location-Based 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

Herman Servatius' Self-dual 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 maxy{b· y | ATy ≤ c and y ≥ 0}. For any solution x to the original linear program and any solution y to the dual we have c · x ≥ (AT y)T x = yT(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 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

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

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):243-262, May 1982.

Colin L. McMaster, An Analysis of Algorithms for the Dutch National Flag Problem, CACM, 21(10):842-846, October 1978.

E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 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 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

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

Author: PEB

R. J. Enbody and H. C. Du, Dynamic Hashing Schemes, ACM Computing Surveys, 20(2):85-113, 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):184-201, 1978.
Per-Åke Larson, Dynamic Hash Tables, CACM 31(4):446-457, 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):738-761, 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 ...)
Smith-Waterman algorithm Solves these problems: matrix-chain multiplication problem, longest common substring, longest common subsequence.

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

Author: CRC-A

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 space-time tradeoffs.

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

 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       