Algorithms and Data Structures Glossary
(Starting with "O")
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
$12 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
O
- O: see big-O notation
- OBDD
- objective function
- oblivious algorithm
- occurrence
- octree
- off-line algorithm
- offset
- omega
- omicron
- one-based indexing
- one-dimensional
- on-line algorithm
- open addressing
- optimal
- optimal cost: see best-case cost
- optimal hashing: see perfect hashing
- optimal merge
- optimal mismatch
- optimal polygon triangulation problem
- optimal polyphase merge
- optimal polyphase merge sort
- optimal solution
- optimal triangulation problem
- optimal value
- optimization problem
- or
- oracle set
- oracle tape
- oracle Turing machine
- order
- ordered array
- ordered binary decision diagram
- ordered linked list
- ordered tree
- order-preserving hash: see linear hash
- order-preserving Huffman coding
- order-preserving minimal perfect hashing
- oriented acyclic graph: see directed acyclic graph
- oriented graph: see directed graph
- oriented tree: see rooted tree
- orthogonal drawing
- orthogonal lists
- orthogonally convex rectilinear polygon
- oscillating merge sort
- out-degree
objective function
(definition)
Definition:
A function associated with an optimization problem which determines how good a solution is, for instance, the total cost of edges in a solution to a traveling salesman problem.
Note:
From Algorithms and Theory of Computation Handbook, page 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
oblivious algorithm
Definition:
An algorithm whose behavior, by design, is independent of some property that influences a typical algorithm for the same problem.
Generalization (I am a kind of ...)
algorithm.
Specialization (... is a kind of me.)
bitonic sort.
Note:
For example, an oblivious sort algorithm always makes the same comparisons, regardless of the input. This is useful for external sorts, since there is a fixed I/O schedule, or parallel algorithms, like bitonic sort.
Other types of oblivious algorithms are cache oblivious, which are not dependent on hardware parameters like cache size and cache-line length, and oblivious routing, which route packets independent of the network topology, the history of traffic flow, or the congestion.
Author: PEB
occurrence
(definition)
Definition:
A string v occurs in a string u if v is a substring of u.
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
octree
(data structure)
Definition:
A tree to index three dimensions. Each node has either eight children or no children.
Note:
If one views a binary tree as partitioning one dimension, a quadtree analogously partitions two dimensions, and an octree partitions three.
Author: PEB
More information
algorithms, another diagram and algorithm, and one more diagram from Martin John Baker. Another diagram from Nilo Stolte.
off-line algorithm
(definition)
Definition:
An algorithm which is given the entire sequence of inputs in advance.
Note:
From Algorithms and Theory of Computation Handbook, pages 10-17 and 19-27, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
offset
(definition)
Definition:
The distance from the beginning of a string to the end of a segment in that string.
Note:
From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
omega
(definition)
Definition:
The Greek letter written as ω (see ω(n)) or Ω (see Ω(n)).
Author: PEB
omicron
(definition)
Definition:
The Greek letter written as "o" (see little-o notation) or "O" (see big-O notation).
Author: PEB
one-based indexing
(definition)
Definition:
Indexing (an array) beginning with 1.
Aggregate parent (I am a part of or used in ...)
array.
Note:
That is, an array A with n items is accessed as A[1], A[2], ..., A[n].
Author: PEB
one-dimensional
(definition)
Definition:
Dealing with or restricted to a line. An organization where location can be completely described with exactly one axis.
Author: PEB
on-line algorithm
(definition)
Definition:
An algorithm that must process each input in turn, without detailed knowledge of future inputs.
Note:
From Algorithms and Theory of Computation Handbook, pages 10-17 and 19-27, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
open addressing
(algorithm)
Definition:
A class of collision resolution schemes in which all items are stored within the hash table. In case of collision, other positions are computed, giving a probe sequence, and checked until an empty position is found. Some ways of computing possible new positions are less efficient because of clustering. Typically items never move once put in place, but in Robin Hood hashing and other techniques, previously placed items may move.
Generalization (I am a kind of ...)
collision resolution scheme.
Specialization (... is a kind of me.)
Probe sequences: linear probing, quadratic probing, double hashing, uniform hashing Placement techniques: Robin Hood hashing.
Aggregate parent (I am a part of or used in ...)
hash table.
Aggregate child (... is a part of or used in me.)
clustering.
Note:
After [CLR90, page 232]. Chaining, the use of external data structures to resolve collisions, has no clustering in the usual sense.
Another technique that may move previously-placed items, like Robin Hood hashing, is LCFS (last come, first served) where the most recent item always displaces an existing item.
Author: PEB
optimal
(definition)
Definition:
(1) A solution to an optimization problem which has the minimum (or maximum) value of the objective function. (2) The time, space, resource, etc. complexity of an algorithm which matches the best known lower bound of a problem.
Author: SKS
optimal merge
(algorithm)
Definition:Merge n sorted sequences of different lengths into one output while minimizing reads. Only two sequences can be merged at once. At each step, the two shortest sequences are merged.
Formal Definition: Let D={n1, ... , nk} be the set of lengths of sequences to be merged. Take the two shortest sequences, ni, nj∈ D, such that n≥ ni and n≥ nj ∀ n∈ D. Merge these two sequences. The new set D is D' = (D - {ni, nj}) ∪ {ni+nj}. Repeat until there is only one sequence.
Note:
Merging sequences by length is the same as joining trees by frequency in Huffman coding. For example, let there be a set of sorted sequences of the following lengths: D={3,5,7,9,12,14,15,17}. Building the optimal merge tree goes as follows. Note that merged sequences are replaced by the sum of their lengths. For instance, the first step merges the sequence of length 3 and the sequence of length 5 to get a sequence of length 8.
3 5 7 9 12 14 15 17 8 7 9 12 14 15 17
/ \
3 5 15 9 12 14 15 17
/ \
8 7
/ \
3 5 15 21 14 15 17
/ \ / \
8 7 9 12
/ \
3 5 29 21 15 17
/ \ / \
14 15 9 12
/ \
8 7
/ \
3 5 29 21 32
/ \ / \ / \
14 15 9 12 15 17
/ \
8 7
/ \
3 5 50 32
/ \ / \
/ \ 15 17
29 21
/ \ / \
14 15 9 12
/ \
8 7
/ \
3 5 82
/ \
/ \
/ \
50 32
/ \ / \
/ \ 15 17
29 21
/ \ / \
14 15 9 12
/ \
8 7
/ \
3 5
Author: AL
optimal mismatch
(algorithm)
Definition:
A string matching algorithm that compares the rarest character first. When a character doesn't match, the next character in the text beyond the search string determines where the next possible match begins.
Note:
After [Sund98].
Author: PEB
optimal polyphase merge
(algorithm)
Definition:
A polyphase merge which seeks to minimize the number of merge passes by allocating output runs of each pass to the various output files. Since polyphase merging must have a different number of runs in each file to be efficient, one seeks the optimal way of selecting how many runs go into each output file. A series of kth order Fibonacci numbers is one way to select the number of runs.
Author: ASK
optimal polyphase merge sort
(algorithm)
Definition:
An external sort algorithm that uses optimal polyphase merges.
Author: PEB
optimal solution
(definition)
Definition:
A solution to an optimization problem which minimizes (or maximizes) the objective function.
Note:
From Algorithms and Theory of Computation Handbook, page 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
optimal triangulation problem
(classic problem)
Definition:
Find the triangulation with the greatest overall minimum angle. There is an incremental algorithm that takes O(n log n) time.
Note:
Triangulation is breaking up an area into triangles. The goal is to make all the triangles as close to equilateral as possible. Equivalently, have as few "slivers" as possible. This is the best triangulation if you want to interpolate a height field (topographic map) between given points, or to divide a surface to triangles and research the heat conduction, etc. between them. Contributed by Motty Porat (vn16908@netvision.net.il) 10 July 2000. See Computational Geometry by De Berg, Van Kreveld, Overmars and Schwarzkopf.
Author: PEB
optimal value
(definition)
Definition:
The minimum (or maximum) value of the objective function over the feasible region of an optimization problem.
Note:
From Algorithms and Theory of Computation Handbook, page 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
optimization problem
(definition)
Definition:
A computational problem in which the object is to find the best of all possible solutions. More formally, find a solution in the feasible region which has the minimum (or maximum) value of the objective function.
Note:
An optimization problem asks, what is the best solution? A decision problem asks, is there a solution with a certain characteristic? For instance, the traveling salesman problem is an optimization problem, while the corresponding decision problem asks if there is a Hamiltonian cycle with a cost less than some fixed amount k.
From Algorithms and Theory of Computation Handbook, pages 29-20 and 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
or
(definition)
Definition:
Disjunction: 0 OR 0 = 0, 0 OR 1 = 1, 1 OR 0 = 1, 1 OR 1 = 1.
Also known as inclusive or.
Note:
Also known as "inclusive or" in contrast to exclusive or (xor).
Author: PEB
oracle set
(definition)
Definition:
A predetermined set of tapes used by an oracle Turing machine to make decisions otherwise not feasibled.
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
oracle tape
(definition)
Definition:
An extra tape used by an oracle Turing machine to make decisions otherwise not feasible.
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
oracle Turing machine
(definition)
Definition:
A Turing machine with an extra oracle tape and three extra states q?, qy, qn. When the machine enters q?, control goes to state qy if the oracle tape content is in the oracle set; otherwise control goes to state qn.
Note:
From Algorithms and Theory of Computation Handbook, pages 24-19 and 28-25, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
order
(definition)
Definition:
(1) The height of a tree. (2) The number of children of the root of a binomial tree. (3) The maximum number of children of nodes in a B-tree. (4) The number of data streams, usually denoted ω, in a multiway merge.
Authors: CRC-A,PEB
ordered array
(data structure)
Definition:
An array whose items have some order. Usually, it means a sorted array, but may mean not fully ordered, for example, all values less than the median are in the first half.
Author: PR
ordered linked list
(data structure)
Definition:
A linked list whose items are kept in some order.
Generalization (I am a kind of ...)
linked list, sorted list.
Specialization (... is a kind of me.)
skip list, jump list.
Author: PR
ordered tree
(data structure)
Definition:
A tree where the children of every node are ordered, that is, there is a first child, second child, third child, etc.
Note:
An unordered tree may be thought of as a recursive bag, while an ordered tree is a recursive list.
Author: PEB
order-preserving Huffman coding
(algorithm)
Definition:
A variable-length character coding based on the frequency of each character. The algorithm is similar to Huffman coding, but the trees are kept in the same order as the characters. Two adjacent trees with the least combined frequency are joined as subtrees of a new root. As with Huffman coding, that new tree is assigned the sum of the subtrees' frequencies. Repeat until all characters are in one tree.
Aggregate child (... is a part of or used in me.)
full binary tree, priority queue, greedy algorithm.
Note:
This may not produce a true Huffman code. Although encoded messages may be up to twice as long as true Huffman codes, order-preserving Huffman codes are "quite effective for most data." [Graef06, page 5]
There are algorithms to produce optimum order-preserving prefix codes, but they are more complicated.
Author: PEB
order-preserving minimal perfect hashing
(algorithm)
Definition:
A minimal perfect hashing function for keys in S such that if k1, k2 ∈ S and k1 > k2, then f(k1) > f(k2).
Generalization (I am a kind of ...)
minimal perfect hashing, linear hash, Las Vegas algorithm.
Note:
For example, if the keys are stored in order in an array, the array offsets are an order preserving minimal perfect hash of the keys.
Author: BJ
More information
Zbigniew J. Czech, George Havas, and Bohdan S. Majewski, An Optimal Algorithm for Generating Minimal Perfect Hash Functions, Information Processing Letters, 43(5):257-264, October 1992. Available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5566. "It uses expected linear time and ... runs very fast in practice."
orthogonal drawing
(definition)
Definition:
A graph drawing in which each edge is represented by a polyline, each segment of which is parallel to a coordinate axis.
Note:
From Algorithms and Theory of Computation Handbook, page 9-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
orthogonal lists
(data structure)
Definition:Lists that share items, but are structurally independent.
Aggregate parent (I am a part of or used in ...)
sparse matrix.
Aggregate child (... is a part of or used in me.)
list.
Note:
The lists are interweaved through items. For instance, we may keep people on three orthogonal lists by hair color, gender, and country of residence or data values in a sparse matrix on two orthogonal lists by row and column. Inserting an item means inserting it into each list as appropriate.
Author: PEB
More information
A picture of a sparse matrix implemented with two orthogonal lists. A lab exercise with four attributes. PowerPoint lecture notes of using orthogonal lists to implement a sparse matrix.
orthogonally convex rectilinear polygon
(definition)
Definition:
A rectilinear polygon P in which every horizontal or vertical segment connecting two points in P lies totally within P.
Note:
From Algorithms and Theory of Computation Handbook, page 20-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
oscillating merge sort
(algorithm)
Definition:
Given n tape drives, one input and n-1 work drives, distribute a portion of the input to n-2 tapes, then merge them onto the final tape reading the n-2 backward. Repeat until n-2 (backward) merged runs have been created, at which time they are merged. Continue building up powers of n-2 batches until done.
Generalization (I am a kind of ...)
external sort.
Author: PEB
More information
Sheldon Sobel, Oscillating Sort-A New Sort Merging Technique, Journal of the ACM, 9(3):372-374, July 1962.
out-degree
(definition)
Definition:
The number of edges going out of a vertex in a directed graph.
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
|
