- Industry: Technology
- Number of terms: 2742
- Number of blossaries: 0
- Company Profile:
The National Institute of Standards and Technology (NIST) — known between 1901 and 1988 as the National Bureau of Standards (NBS) — is a measurement standards laboratory and a non-regulatory agency of the United States Department of Commerce. The institute's official mission is to promote U.S. ...
A divide and conquer paradigm in which partial results from recursive calls can be used before the calls complete. The technique is often useful for reducing the depth of an algorithm.
Industry:Computer science
A division of a set into nonempty disjoint sets that completely cover the set. In other words, a partition P of a set S is a set of subsets with the following properties:
* ∀ s<sub>i</sub> ∈ P, s<sub>i</sub> ≠ ø <br />(no subset is empty), <li> ∀ s<sub>i</sub>, s<sub>j</sub> ∈ P, i ≠ j → s<sub>i</sub> ∩ s<sub>j</sub> = ø <br /> (subsets are disjoint), and <li> U<sub>i=1</sub> s<sub>i</sub> = S <br />(subsets exactly cover the original).
Industry:Computer science
A dynamic hashing table that grows a few slots at a time. It uses a hash function, h, with a range of (0,1). For a key, k, an intermediate value, x=⌈ S-h(k)⌉ +h(k), is computed to find the final slot, ⌊ d<sup>x</sup>⌋, where d>1 is called the growth factor. To increase the number of slots, increase S to S' and rehash any keys from ⌊ d<sup>S</sup>⌋ to ⌊ d<sup>S'</sup>⌋-1.
Industry:Computer science
A dynamic hashing table that grows one slot at a time. It has a family of hash functions, h<sub>i</sub>, where the range of h<sub>i+1</sub> is twice the range of h<sub>i</sub>. Slots below a pointer, p, have been split. That is, key, k, is in slot h<sub>i</sub>(k) if h<sub>i</sub>(k) > p. Otherwise it is in h<sub>i+1</sub>(k). To maintain the load factor, slot p can be split (rehashed with h<sub>i+1</sub>) and p incremented. When p reaches the end, the ranges are doubled (i is incremented), and p starts over.
Industry:Computer science
A dynamic hashing table that grows one slot at a time. It has a family of hash functions, h<sub>i</sub>, where the range of h<sub>i+1</sub> is twice the range of h<sub>i</sub>. Slots below a pointer, p, have been split. That is, key, k, is in slot h<sub>i</sub>(k) if h<sub>i</sub>(k) > p. Otherwise it is in h<sub>i+1</sub>(k). To maintain the load factor, slot p can be split (rehashed with h<sub>i+1</sub>) and p incremented. When p reaches the end, the ranges are doubled (i is incremented), and p starts over.
Industry:Computer science
A facility location problem in which the supply points must be a subset of demand points.
Industry:Computer science
A fast priority queue implementation having N buckets each with width w, or covering w time. An item with priority p more than current goes in bucket (p/w)%N. Choose N and w to have few items in each bucket. Keep items sorted within buckets. Double or halve N and change w if the number of items grows or shrinks a lot.
Industry:Computer science
A figure of merit for a family of searches, the "best" is the search that takes the minimum accesses in the worst case.
Industry:Computer science
A file which stores keys and an index into another file. The index file may have additional structure, e.g., be a B-tree.
Industry:Computer science
