Algorithms and Data Structures Glossary (Starting with "W")
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
W
 walk
 weakheap
 weakheap sort
 weightbalanced tree: see BB(α) tree
 weighted, directed graph
 weighted graph
 window
 witness
 work
 workdepth model
 workefficient
 workpreserving
 worst case
 worstcase cost
 worstcase minimum access
walk
(definition)
Definition:
A path in which edges may be repeated.
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
weakheap
(data structure)
Definition:
A relaxed heap satisfying the following three conditions: (1) every key in the right subtree of a node is greater than the key stored in the node itself, (2) the root has no left child, and (3) leaves are only found on the last two levels of the tree.
Note:
A weakheap may be efficiently implemented with an array a of items and an array r of reverse bits. The left child of an index i is at index 2i+1r_{i}, and the right child is at index 2i+r_{i}.
This is a minimum weakheap. A maximum weakheap has subtree keys that are less than the node's key.
Author: SE
weakheap sort
(algorithm)
Definition:
A sort algorithm that builds a weakheap, then repeatedly extracts the maximum item. In the worst case, the run time is O(n log n + 0.1 n).
Author: PEB
weighted, directed graph
(definition)
Definition:
A directed graph that has a weight, or numeric value, associated with each edge.
Generalization (I am a kind of ...)
directed graph, weighted graph.
Author: PEB
weighted graph
(definition)
Definition:
A graph having a weight, or number, associated with each edge. Some algorithms require all weights to be nonnegative, integral, positive, etc.
Also known as edgeweighted graph.
Generalization (I am a kind of ...)
labeled graph.
Specialization (... is a kind of me.)
weighted, directed graph.
Author: PEB
window
(definition)
Definition:substring of the text that is aligned with the pattern.
Note:
From Algorithms and Theory of Computation Handbook, page 1126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
witness
(definition)
Definition:
(1) a structure providing an easily verified bound on the optimal value of an optimization problem. Typically used in the analysis of an approximation algorithm to prove the performance guarantee. (2) a mismatch of two symbols of string y at a distance of d is a "witness" to the fact that in no subject y could occur twice at a distance of exactly d positions (equivalently, that d cannot be a period of y).
Note:
From Algorithms and Theory of Computation Handbook, pages 1317 and 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
work
(definition)
Definition:
The total number of operations taken by a computation.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
workdepth model
(definition)
Definition:
A model of parallel computation in which one keeps track of the total work and depth of a computation without worrying about how it maps onto a machine.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
workefficient
(definition)
Definition:
A parallel algorithm which asymptotically requires at most a constant factor more work than the best known sequential algorithm or the optimal work.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
workpreserving
(definition)
Definition:
A translation of an algorithm from one model of computation to another in which the work is the same in both models, to within a constant factor.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
worst case
(definition)
Definition:
(1) The situation or input that forces an algorithm or data structure to take the most time or resources. (2) Having to do with this situation or input.
Note:
See the notes on worstcase behavior at Huffman coding and balanced quicksort and the link at BB(α) tree.
Author: PEB
worstcase cost
(definition)
Definition:
The highest possible use of resources of an algorithm, which occurs for the most pessimistic, or worst possible, input.
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
worstcase minimum access
(definition)
Definition:
A figure of merit for a family of searches, the "best" is the search that takes the minimum accesses in the worst case.
Author: AB
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
