- 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. ...
An efficient 3-pass refinement of a bucket sort algorithm. The first pass counts the number of items for each bucket in an auxiliary array, and then makes a running total so each auxiliary entry is the number of preceding items. The second pass puts each item in its proper bucket according to the auxiliary entry for the key of that item. The last pass sorts each bucket.
Industry:Computer science
An efficient algorithm to render a line with pixels. The long dimension is incremented for each pixel, and the fractional slope is accumulated.
Industry:Computer science
An efficient algorithm to solve the single-source shortest-path problem. Weights may be negative. The algorithm initializes the distance to the source vertex to 0 and all other vertices to ∞. It then does V-1 passes (V is the number of vertices) over all edges relaxing, or updating, the distance to the destination of each edge. Finally it checks each edge again to detect negative weight cycles, in which case it returns false. The time complexity is O(VE), where E is the number of edges.
Industry:Computer science
An efficient algorithm to solve the single-source shortest-path problem. Weights may be negative. The algorithm initializes the distance to the source vertex to 0 and all other vertices to ∞. It then does V-1 passes (V is the number of vertices) over all edges relaxing, or updating, the distance to the destination of each edge. Finally it checks each edge again to detect negative weight cycles, in which case it returns false. The time complexity is O(VE), where E is the number of edges.
Industry:Computer science
An efficient implementation of a priority queue. The linear hash function monotonically maps keys to buckets, and each bucket is a heap.
Industry:Computer science
An efficient implementation of priority queues where insert, delete, get minimum, get maximum, etc. take O(log log N) time, where N is the total possible number of keys. Depending on the circumstance, the implementation is null (if the queue is empty), an integer (if the queue has one integer), a bit vector of size N (if N is small), or a special data structure: an array of priority queues, called the bottom queues, and one more priority queue of array indexes of the bottom queues.
Industry:Computer science
An efficient, in-place variant of radix sort that distributes items into hundreds of buckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step. The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes". Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
Industry:Computer science
An entry reachable for a (d-1)-extremal entry through a unit vertical, horizontal, or diagonal-mismatch step.
Industry:Computer science
An expression consisting solely of boolean variables and values and boolean operations, such as and, or, not, implies, etc.
Industry:Computer science
An expression of the most the result of an approximation algorithm may depart from the optimal solution.
Industry:Computer science
