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

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

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

### W

walk
weak-heap
weak-heap sort
weight-balanced tree: see BB(α) tree
weighted, directed graph
weighted graph
window
witness
work
work-depth model
work-efficient
work-preserving
worst case
worst-case cost
worst-case minimum access

#### 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-ri, and the right child is at index 2i+ri.

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.

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

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

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

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

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

 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