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

Free glossaries at TanslationDirectory.com

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

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

walk

(definition)

Definition: A path in which edges may be repeated.

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

weak-heap

(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 weak-heap 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+1-r_i, and the right child is at index 2i+r_i.

This is a minimum weak-heap. A maximum weak-heap has subtree keys that are less than the node's key.

Author: SE

weak-heap sort

(algorithm)

Definition: A sort algorithm that builds a weak-heap, 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 edge-weighted 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 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

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

Author: CRC-A

work

(definition)

Definition: The total number of operations taken by a computation.

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

Author: CRC-A

work-depth 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.

Author: CRC-A

work-efficient

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

Author: CRC-A

work-preserving

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

Author: CRC-A

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 worst-case behavior at Huffman coding and balanced quicksort and the link at BB(α) tree.

Author: PEB

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