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 bigO notation
 OBDD
 objective function
 oblivious algorithm
 occurrence
 octree
 offline algorithm
 offset
 omega
 omicron
 onebased indexing
 onedimensional
 online algorithm
 open addressing
 optimal
 optimal cost: see bestcase 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
 orderpreserving hash: see linear hash
 orderpreserving Huffman coding
 orderpreserving 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
 outdegree
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 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 cacheline 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 1126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
offline algorithm
(definition)
Definition:
An algorithm which is given the entire sequence of inputs in advance.
Note:
From Algorithms and Theory of Computation Handbook, pages 1017 and 1927, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 littleo notation) or "O" (see bigO notation).
Author: PEB
onebased 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
onedimensional
(definition)
Definition:
Dealing with or restricted to a line. An organization where location can be completely described with exactly one axis.
Author: PEB
online 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 1017 and 1927, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 previouslyplaced 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={n_{1}, ... , n_{k}} be the set of lengths of sequences to be merged. Take the two shortest sequences, n_{i}, n_{j}∈ D, such that n≥ n_{i} and n≥ n_{j} ∀ n∈ D. Merge these two sequences. The new set D is D' = (D  {n_{i}, n_{j}}) ∪ {n_{i}+n_{j}}. 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 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2920 and 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
oracle Turing machine
(definition)
Definition:
A Turing machine with an extra oracle tape and three extra states q_{?}, q_{y}, q_{n}. When the machine enters q_{?}, control goes to state q_{y} if the oracle tape content is in the oracle set; otherwise control goes to state q_{n}.
Note:
From Algorithms and Theory of Computation Handbook, pages 2419 and 2825, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 Btree. (4) The number of data streams, usually denoted ω, in a multiway merge.
Authors: CRCA,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
orderpreserving Huffman coding
(algorithm)
Definition:
A variablelength 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, orderpreserving Huffman codes are "quite effective for most data." [Graef06, page 5]
There are algorithms to produce optimum orderpreserving prefix codes, but they are more complicated.
Author: PEB
orderpreserving 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):257264, 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 923, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2026, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
oscillating merge sort
(algorithm)
Definition:
Given n tape drives, one input and n1 work drives, distribute a portion of the input to n2 tapes, then merge them onto the final tape reading the n2 backward. Repeat until n2 (backward) merged runs have been created, at which time they are merged. Continue building up powers of n2 batches until done.
Generalization (I am a kind of ...)
external sort.
Author: PEB
More information
Sheldon Sobel, Oscillating SortA New Sort Merging Technique, Journal of the ACM, 9(3):372374, July 1962.
outdegree
(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
