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

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

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

### U

UB-tree
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 B-tree: see UB-tree
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 NP-hard 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 vt > 0 and weight wt > 0. Find the number nt > 0 of each type of item such that they fit, ∑t=1N ntwt ≤ c, and the total value, ∑t=1N ntvt, 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 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

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

Author: CRC-A

#### undecidable problem

(definition)

Definition: A problem that cannot be solved for all cases by any algorithm whatsoever---equivalently, 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 24-19 or 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 self-loops, 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 27-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

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

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

Author: CRC-A

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

#### 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 24-19 and 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 doubly-ended 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 doubly-ended 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.

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

Author: CRC-A

#### 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
j
i 1776
-911
--88
---1

It may be more compactly represented in an array by storing entry (i,j) in location n(i-1) + j - i(i-1)/2 = (2n-i)(i-1)/2 + j one-based indexing.

Author: PEB

 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

 Use More Glossaries Use Free Dictionaries Use Free Translators Submit Your Glossary Read Translation Articles Register Translation Agency Submit Your Resume Obtain Translation Jobs Subscribe to Free Newsletter Buy Database of Translators Obtain Blacklisted Agencies Vote in Polls for Translators Read News for Translators Advertise Here Read our FAQ Read Testimonials Use Site Map