Algorithms and Data Structures Glossary (Starting with "U")
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
$8 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
U
 UBtree
 UKP: see unbounded knapsack problem
 unary function
 unbounded knapsack problem
 uncomputable function
 uncomputable problem
 undecidable language
 undecidable problem
 undirected graph
 uniform circuit complexity
 uniform circuit family
 uniform hashing
 uniform matrix
 union
 union of automata
 universal Btree: see UBtree
 universal hashing
 universal state
 universal Turing machine
 universe
 UnShuffle sort
 unsolvable problem
 unsorted list
 upper triangular matrix
unary function
(definition)
Definition:
A function which takes one argument.
Author: PEB
unbounded knapsack problem
(classic problem)
Definition:
Given types of items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume. The number of items of each type is unbounded. This is an NPhard combinatorial optimization problem.
Formal Definition: There is a knapsack of capacity c > 0 and N types of items. Each item of type t has value v_{t} > 0 and weight w_{t} > 0. Find the number n_{t} > 0 of each type of item such that they fit, ∑_{t=1}^{N} n_{t}w_{t} ≤ c, and the total value, ∑_{t=1}^{N} n_{t}v_{t}, is maximized.
Also known as UKP.
Author: PEB
uncomputable function
(definition)
Definition:
A function that cannot be computed by any algorithm  equivalently, not by any Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, page 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
undecidable language
(definition)
Definition:
A language for which the membership cannot be decided by an algorithm  equivalently, cannot be recognized by a Turing machine that halts for all inputs.
Note:
From Algorithms and Theory of Computation Handbook, page 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
undecidable problem
(definition)
Definition:
A problem that cannot be solved for all cases by any algorithm whatsoeverequivalently, whose associated language cannot be recognized by a Turing machine that halts for all inputs.
Specialization (... is a kind of me.)
halting problem, Post's correspondence problem.
Note:
From Algorithms and Theory of Computation Handbook, page 2419 or 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
undirected graph
(data structure)
Definition:
A graph whose edges are unordered pairs of vertices. That is, each edge connects two vertices.
Formal Definition: A graph G is a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {{u,v}  u, v ∈ V}. If the graph does not allow selfloops, adjacency is irreflexive, that is E ⊆ {{u,v}  u, v ∈ V ∧ u ≠ v}.
Note:
An undirected graph may be represented as a directed graph with two directed edges, one "to" and one "from," for each undirected edge.
Author: PEB
uniform circuit complexity
(definition)
Definition:
The study of complexity classes defined by uniform circuit families.
Note:
From Algorithms and Theory of Computation Handbook, page 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
uniform circuit family
(definition)
Definition:
A sequence of circuits, one for each input length n, that can be efficiently generated by a Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, page 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
uniform hashing
(algorithm)
Definition:
A conceptual method of open addressing for a hash table. A collision is resolved by putting the item in the next empty place given by a probe sequence which is independent of sequences for all other key.
Note:
Since the probe sequences are independent, this is free of clustering. This is conceptual because real probe sequences are unlikely to be completely independent.
Author: PEB
uniform matrix
(data structure)
Definition:
A matrix having the same number of items in each row.
Specialization (... is a kind of me.)
square matrix, rectangular matrix.
Author: PEB
union
(definition)
Definition:
The union of two sets is a set having all members in either set.
Note:
The union of {2, 3, 5} and {7, 5, 8} is {2, 3, 5, 7, 8}.
Author: PEB
union of automata
(algorithm)
Definition:
Find an automaton that accepts everything which the automata accept individually.
Author: PEB
universal hashing
(definition)
Definition:
A scheme that chooses randomly from a set of hash functions.
Note:
From Algorithms and Theory of Computation Handbook, page 214, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
universal state
(definition)
Definition:
A state in an alternating Turing machine from which the machine accepts only if all possible moves lead to acceptance.
Note:
From Algorithms and Theory of Computation Handbook, page 2418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
universal Turing machine
(definition)
Definition:
A Turing machine that is capable of simulating any other Turing machine by encoding the latter.
Note:
From Algorithms and Theory of Computation Handbook, pages 2419 and 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
universe
(definition)
Definition:
All potential elements of a set.
Author: PEB
UnShuffle sort
(algorithm)
Definition:
A distribution sort with two phases. In the first phase, the inputs are distributed among doublyended queues keeping the items in each queue ordered and creating a new queue when there is no place on an existing queue. The second phase is an ideal merge in which the item to be removed is determined by keeping the queues in a priority queue.
Generalization (I am a kind of ...)
distribution sort.
Aggregate child (... is a part of or used in me.)
ideal merge, pile, priority queue.
Note:
The doublyended queue with ordered items is called a pile. The UnShuffle algorithm is the most efficient available for sorting data streams that exhibit low entropy, i.e., are already mostly sorted or contains runs of sorted elements. The run time is Θ(N) for sorted input. The general case is NK/2 + N log K where K is the entropy of the input and is manifest in the number of piles generated during the distribution phase.
Author: ASK
More information
Art S. Kagel, Unshuffle Algorithm, Not Quite a Sort?, Computer Language Magazine, 3(11), November 1985.
unsolvable problem
(definition)
Definition:
A computational problem that cannot be solved by a Turing machine. The associated function is called an uncomputable function.
Note:
From Algorithms and Theory of Computation Handbook, page 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
unsorted list
(definition)
Definition:
A list whose order of items, if any, is not known.
Note:
The list need not be out of order, simply that it is not known to be in order.
Author: PR
upper triangular matrix
(data structure)
Definition:
A matrix that is only defined at (i,j) when i ≤ j.
Generalization (I am a kind of ...)
matrix.
Specialization (... is a kind of me.)
strictly upper triangular matrix.
Note:
For example It may be more compactly represented in an array by storing entry (i,j) in location n(i1) + j  i(i1)/2 = (2ni)(i1)/2 + j onebased indexing.
Author: PEB
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
