Algorithms and Data Structures Glossary
(Starting with "P")
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
P
- P
- packing
- padding argument
- pagoda
- pairing heap
- PAM: see point access method
- parallel computation thesis
- parallel prefix computation
- parallel random-access machine
- parametric searching
- parent
- partial function
- partially decidable problem
- partially dynamic graph problem
- partially ordered set: see poset
- partially persistent data structure
- partial order
- partial recursive function
- partition
- passive data structure
- path
- path cover
- path system problem
- Patricia tree
- pattern
- pattern element
- P-complete
- PCP: see Post's correspondence problem
- PDA: see pushdown automaton
- Pearson's hash
- perfect binary tree
- perfect hashing
- perfect k-ary tree
- perfect matching
- perfect shuffle
- performance guarantee
- performance ratio: see relative performance guarantee
- permutation
- persistent data structure
- phonetic coding
- pigeonhole sort
- pile
- pipelined divide and conquer
- planar graph
- planarization
- planar straight-line graph
- PLOP-hashing
- point access method
- pointer jumping
- pointer machine
- poissonization
- polychotomy
- polyhedron
- polylogarithmic
- polynomial
- polynomial approximation scheme
- polynomial hierarchy
- polynomial time
- polynomial-time reduction
- polyphase merge
- polyphase merge sort
- polytope
- poset
- postfix traversal: see postorder traversal
- Post machine
- postman's sort
- postorder traversal
- Post's correspondence problem
- potential function
- PRAM: see parallel random-access machine
- predicate
- prefix
- prefix code
- prefix computation
- prefix sums: see scan
- prefix traversal: see preorder traversal
- preorder traversal
- primary clustering
- primitive recursive
- Prim-Jarnik algorithm
- principle of optimality
- priority queue
- prisoner's dilemma
- PRNG: see pseudo-random number generator
- probabilistic algorithm
- probabilistically checkable proof
- probabilistic Turing machine
- probe sequence
- procedure
- process algebra
- proper
- proper binary tree: see full binary tree
- proper coloring
- proper subset
- property list: see dictionary
- prune and search
- pseudo-random number generator
- PTAS: see polynomial approximation scheme
- pth order Fibonacci numbers: see kth order Fibonacci numbers
- P-tree
- purely functional language
- pushdown automaton
- pushdown transducer
- p-way merge sort: see k-way merge sort
P
(definition)
Definition:
The complexity class of languages that can be accepted by a deterministic Turing machine in polynomial time.
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
More information
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Wikipedia entry on Complexity classes P and NP. Scott Aaronson's Complexity Zoo
packing
(definition)
Definition:
Given a finite collection of subsets of a finite ground set, to find an optimal subcollection that are pairwise disjoint.
Note:
From Algorithms and Theory of Computation Handbook, page 32-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
padding argument
(definition)
Definition:
A method for transferring results about one complexity bound to another complexity bound, by padding extra dummy characters onto the inputs of the machines involved.
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
pagoda
(data structure)
Definition:
A priority queue implemented with a variant of a binary tree. The root points to its children, as in a binary tree. Every other node points back to its parent and down to its leftmost (if it is a right child) or rightmost (if it is a left child) descendant leaf. The basic operation is merge or meld, which maintains the heap property. An element is inserted by merging it as a singleton. The root is removed by merging its right and left children. Merging is bottom-up, merging the leftmost edge of one with the rightmost edge of the other.
Generalization (I am a kind of ...)
priority queue.
Aggregate child (... is a part of or used in me.)
binary tree, heap property, meld.
Author: PEB
More information
J. Francon, G. Viennot, and J. Vuillemin, Description and analysis of an efficient priority queue representation, Proc. 19th Annual Symp. on Foundations of Computer Science. IEEE, 1978, pages 1-7.
R. Nix, An Evaluation of Pagodas, Res. Rep. 164, Dept. of Computer Science, Yale Univ. 1988?
parallel computation thesis
(definition)
Definition:
Sequential space is a polynomial of parallel time.
Note:
From Algorithms and Theory of Computation Handbook, page 45-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
parallel prefix computation
(algorithm)
Definition:
Calculate an associative function, f, on all prefixes of an n-element array, that is, s[0], f(s[0], s[1]), f(s[0], f(s[1], s[2])), ..., f(s[0], f(s[1], ... f(s[n-2], s[n-1])...)), using Θ(n) processors in Θ(log n) time. The algorithm is
for j := 0 to lg(n)-1 do
for i := 2j to n-1 parallel-do
s[i] := f(s[i-2j], s[i]) where lg is the logarithm base 2, and parallel-do does the innermost computations in parallel.
Note:
In particular, this calculates any associative function, such as sum, maximum, or concatenate, over a list of values in logarithmic time. Note the write-after-read hazards in the parallel-do loop: old values of s[2j] to s[n-1-2j] must be read before being overwritten. Since this algorithm overwrites the initial values, the n processors can copy input values to a result array in parallel in one additional step.
From Yair Tuaff (r56409@email.sps.mot.com), 29 December 1999.
Author: PEB
parallel random-access machine
(definition)
Definition:
A shared memory model of computation, where typically the processors all execute the same instruction synchronously, and access to any memory location occurs in unit time.
Also known as PRAM.
Aggregate child (... is a part of or used in me.)
shared memory.
Note:
From Algorithms and Theory of Computation Handbook, page 47-3, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
parent
(definition)
Definition:
Of a node: the tree node conceptually above or closer to the root than the node and which has a link to the node. See the figure at tree.
Note:
By definition, a parent node is an internal node.
Author: PEB
partial function
(definition)
Definition:
A function which is not defined for some inputs of the right type, that is, for some of a domain. For instance, division is a partial function since division by 0 is undefined (on the Reals).
Note:
This definition says a function is either partial or total, but not both. Some authors consider that all functions are partial, but some are total, too.
Author: PEB
partially decidable problem
(definition)
Definition:
One whose associated language is a recursively enumerable language. Equivalently, there exists an algorithm that halts and outputs 1 for every instance having a "yes" answer, but for instances having a "no" answer is allowed either not to halt or to halt and output 0.
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
partially dynamic graph problem
(definition)
Definition:
Problem where the update operations include either edge insertions (incremental) or deletions (decremental).
Note:
From Algorithms and Theory of Computation Handbook, page 8-22, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
partially persistent data structure
(definition)
Definition:
A persistent data structure that allows updates to the latest version only.
Note:
From Algorithms and Theory of Computation Handbook, page 5-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
partial order
(definition)
Definition:
An order defined for some, but not necessarily all, pairs of items. For instance, the sets {a, b} and {a, c, d} are subsets of {a, b, c, d}, but neither is a subset of the other. So "subset of" is a partial order on sets.
Formal Definition: A partial order is a binary relation that is reflexive, transitive, and antisymmetric.
Authors: PEB,PJT
partial recursive function
(definition)
Definition:
A function computed by a Turing machine that need not halt 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
partition
(definition)
Definition:
(1) A division of a set into nonempty disjoint sets that completely cover the set. (2) To rearrange the elements of an array into two (or more) groups, typically, such that elements in the first group are less than a value and elements in the second group are greater.
Formal Definition: (1) A partition P of a set S is a set of subsets with the following properties: - ∀ si ∈ P, si ≠ ø
(no subset is empty), - ∀ si, sj ∈ P, i ≠ j → si ∩ sj = ø
(subsets are disjoint), and - Ui=1 si = S
(subsets exactly cover the original). Thanks to Julio A. Cartaya <jac@puma.mt.att.com>.
Generalization (I am a kind of ...)
set.
Specialization (... is a kind of me.)
select and partition.
Aggregate parent (I am a part of or used in ...)
quicksort, Dutch national flag, American flag sort.
Author: PEB
passive data structure
(data structure)
Definition:
A data structure that is only changed by external threads or processes, in contrast to an active data structure.
Note:
See the note for active data structure for an example.
Author: PEB
path
(definition)
Definition:
A list of vertices of a graph where each vertex has an edge from it to the next vertex.
Specialization (... is a kind of me.)
simple path, shortest path, cycle, Hamiltonian cycle, Euler cycle, alternating path.
Note:
A path is usually assumed to be a simple path, unless otherwise defined.
Author: PEB
path system problem
(classic problem)
Definition:
For a path system P=(x,R,S,T), where S⊆ X, T ⊆ X, and R⊆ X × X × X, the problem of whether there is an admissible vertex in S. A vertex is admissible if and only if x∈ T, or there exists admissible y, z ∈ X such that (x,y,z) ∈ R.
Note:
From Algorithms and Theory of Computation Handbook, page 45-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
Patricia tree
(data structure)
Definition:
A compact representation of a trie in which any node that is an only child is merged with its parent.
Also known as radix tree.
Generalization (I am a kind of ...)
trie.
Specialization (... is a kind of me.)
suffix tree.
Note:
A compact directed acyclic word graph (DAWG) merges common suffix trees to save additional space.
A radix tree is taken to be a binary Patricia tree.
Author: SE
More information
Donald R. Morrison, PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, Journal of the ACM, 15(4):514-534, October 1968.
pattern
(definition)
Definition:
A finite number of strings that are searched for in texts.
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
pattern element
(definition)
Definition:
A positive (negative) pattern element is a "partial wild card" presented as a subset of the alphabet Σ, with the symbols in the subset specifying which symbols of Σ are matched (mismatched) by the pattern element.
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
P-complete
(definition)
Definition:
A language L is P-hard under NC many-one reducibility if L' ≤mNC for every L' ∈ P. A language L is P-complete under NC reducibility if L ∈ P and L is P-hard.
Note:
From Algorithms and Theory of Computation Handbook, page 45-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
Pearson's hash
(algorithm)
Definition:
A hash function that uses an auxiliary array, but no shift or exclusive-or (xor) operations.
Generalization (I am a kind of ...)
hash function.
Note:
This hash function may be particularly fast on computers that don't have hardware support for shifting or xor. Careful choice of the auxiliary table allows construction of a perfect hashing function, a minimal perfect hashing function, or even an order-preserving minimal perfect hashing function.
Author: PEB
More information
Peter K. Pearson, Fast Hashing of Variable-Length Text Strings, CACM, 33(6):677-680, June 1990.
perfect binary tree
(definition)
Definition:
A binary tree with all leaf nodes at the same depth. All internal nodes have degree 2.
Generalization (I am a kind of ...)
full binary tree, complete binary tree.
Note:
A perfect binary tree has 2n+1-1 nodes, where n is the height. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2. After LK. A complete binary tree may be seen as a perfect binary tree with some extra leaf nodes at depth n+1, all toward the left. (After [CLR90, page 140]).
This kind of tree is called "complete" by some authors ([CLR90, page 95], Leighton) and "full" by others (Budd page 331, Carrano & Prichard page 429, Ege, [HS83, page 225], and Sahni page 461).
Authors: YZ,PEB
perfect hashing
(algorithm)
Definition:
A hash function that maps each different key to a distinct integer. Usually all possible keys must be known beforehand. A hash table that uses a perfect hash has no collisions.
Formal Definition: A function f is perfect for a set of keys K iff ∀ j, k ∈ K f(j) = f(k) → j = k.
Also known as optimal hashing.
Specialization (... is a kind of me.)
minimal perfect hashing, order-preserving minimal perfect hashing.
Note:
After BJ.
Author: PEB
More information
Martin Dietzfelbinger, Anna Karlin, Kurt Melhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, and Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM J. Comput., 23(4):738-761, August 1994.
perfect k-ary tree
(definition)
Definition:
A k-ary tree with all leaf nodes at same depth. All internal nodes have degree k.
Note:
Called "complete" by [CLR90, page 95].
Author: PEB
perfect matching
(definition)
Definition:
A matching, or subset of edges without common vertices, of a connected graph that touches all vertices exactly once. A graph with an odd number of vertices is allowed one unmatched vertex.
Specialization (... is a kind of me.)
bipartite matching.
Aggregate parent (I am a part of or used in ...)
Christofides algorithm.
Note:
The term comes from matching each vertex with exactly one other vertex. Any perfect matching of a graph with n vertices has n/2 edges. If a graph has a Hamiltonian cycle, it has two different perfect matchings, since the edges in the cycle could be alternately colored. After Douglas Bass (dbass@stthomas.edu) 5 Sep 1999.
Author: PEB
perfect shuffle
(algorithm)
Definition:
Split a list of elements (or deck of cards) exactly in half then precisely interleave the two halves.
Generalization (I am a kind of ...)
deterministic algorithm.
Author: PEB
More information
Historical Note
For several years I defined "perfect shuffle" to mean an algorithm that randomly shuffles (permutes) elements with a uniform chance of getting any particular permutation. I now call that an "ideal random shuffle", after Oleg, since "perfect shuffle" has been far more widely used for decades to mean the above (see for instance, Donald E. Knuth, "The Art of Computer Programming", 2nd edition, Vol 3, Exercises for Sect. 5.3.4, number 13, page 237).
performance guarantee
(definition)
Definition:
An expression of the most the result of an approximation algorithm may depart from the optimal solution.
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
permutation
(algorithm)
Definition:
A rearrangement of elements, where none are lost, added, or changed. The Fisher-Yates shuffle randomly permutes elements.
Also known as shuffle.
Generalization (I am a kind of ...)
combination.
Specialization (... is a kind of me.)
ideal random shuffle, Fisher-Yates shuffle, Johnson-Trotter, sort, derangement.
Aggregate parent (I am a part of or used in ...)
American flag sort.
Note:
A sort is a permutation where the items are arranged in some order. A derangement is a permutation where no item is in its original position.
There are n! permutations of n (distinguishable) elements.
Author: PEB
persistent data structure
(definition)
Definition:
A data structure that preserves its old versions, that is, previous versions may be queried in addition to the latest version.
Specialization (... is a kind of me.)
partially persistent data structure, fully persistent data structure, confluently persistent data structure.
Note:
From Algorithms and Theory of Computation Handbook, page 5-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
More information
James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan, Making Data Structures Persistent, Journal of Computer and System Sciences, 38(1):86-124, 1989.
phonetic coding
(classic problem)
Definition:
Code a string based on how it is pronounced.
Specialization (... is a kind of me.)
double metaphone, Jaro-Winkler, Caverphone, NYSIIS, soundex.
Note:
Because spelling variants of names are common in English, algorithms have been developed to code names based on how they sound. Searching and matching is done by converting a name to some phonetic coding, and comparing codings. If I type "Hansen" into my electronic telephone book, it is useful for it to offer "Hanson" as a possible match. Levenshtein distance and other measures or algorithms allowing for spelling errors usually have sophisticated matching routines, rather than preprocessing the names.
Author: PEB
pigeonhole sort
(algorithm)
Definition:
A 2-pass sort algorithm that is efficient when the range of keys is approximately equal to the number of items. The first pass allocates an array of buckets, one bucket for each possible key value, then moves each item to its key's bucket. The second pass goes over the bucket array moving each item to the next place in the destination.
Generalization (I am a kind of ...)
range sort.
Specialization (... is a kind of me.)
rapid sort.
Note:
The bucket array is called the pigeonhole array. Pigeonhole sort moves items twice: once to the bucket array and again to the final destination. Counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there. Since rapid sort only sorts keys, "moving an item in its key's bucket" is just incrementing a count and "moving each item to the destination" is writing the proper number of keys.
Author: PEB
pile
(data structure)
Definition:
An ordered deque, that is, items may only be added to or removed from the head or the tail. An item is added to the head if it is smaller than the current head. An item is added to the tail if it is greater than the current tail. Items are never inserted into the middle, rather, an additional pile may be created.
Author: ASK
pipelined divide and conquer
(algorithmic technique)
Definition:
A divide and conquer paradigm in which partial results from recursive calls can be used before the calls complete. The technique is often useful for reducing the depth of an algorithm.
Note:
From Algorithms and Theory of Computation Handbook, page 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
planar graph
(definition)
Definition:
A graph that can be drawn in the plane with no crossing edges.
Generalization (I am a kind of ...)
graph.
Specialization (... is a kind of me.)
dual, planar straight-line graph.
Note:
Equivalently, a graph that does not contain any subgraph homeomorphic to the complete graph on 5 vertices or the complete bipartite graph with 3 vertices in each partition.
Author: JLG
planarization
(definition)
Definition:
The process of transforming a graph into a planar graph. More formally, the transformation involves either removing edges (planarization by edge removal), or replacing pairs of nonincident edges by 4-starts (planarization by adding crossing vertices). In both cases, the aim of planarization is minimize the number of edge removals or replacements.
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
planar straight-line graph
(definition)
Definition:
A graph that can be embedded in the plane without crossings in which every edge in the graph is a straight line segment. It is sometimes referred to as planar subdivision or map.
Note:
From Algorithms and Theory of Computation Handbook, page 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
PLOP-hashing
(data structure)
Definition:
Piecewise linear order-preserving (PLOP) hashing is a spatial access method which splits space into a nonperiodic grid. Each spatial dimension is divided by nodes of a binary tree. Object are stored in the grid cell of their centroid.
Note:
After [GG98].
Author: PEB
point access method
(definition)
Definition:
A data structure and associated algorithms primarily to search for points defined in multidimensional space.
Also known as PAM.
Specialization (... is a kind of me.)
EXCELL, grid file, hB-tree, twin grid file, two-level grid file, k-d tree, BSP-tree, quadtree, UB-tree, buddy tree, locality-sensitive hashing.
Note:
After [GG98].
Author: PEB
pointer jumping
(definition)
Definition:
In a linked structure, replacing a pointer with the pointer it points to. Used for various algorithms on lists and trees.
Also known as recursive doubling, shortcutting.
Note:
The name "recursive doubling" comes the fact that if all the pointers are jumped at every step, the pointers cover double the distance with each recursion.
From Algorithms and Theory of Computation Handbook, page 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
pointer machine
(definition)
Definition:
A model of computation whose memory consists of an unbounded collection of registers, or records, connected by pointers. Each register may contain an arbitrary amount of additional information. No arithmetic is allowed to compute the address of a register. The only way to access a register is by following pointers.
Note:
From Algorithms and Theory of Computation Handbook, page 5-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
poissonization
(definition)
Definition:
To replace a deterministic input by poisson process, changing the model into a poisson model. A solution to the poisson model must be interpreted in the original model.
Note:
From Algorithms and Theory of Computation Handbook, page 14-35, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
polychotomy
(definition)
Definition:
Division into many distinct classifications.
Note:
Compare "dichotomy": a division into two distinct, contrasting classes. The term is used in the area of machine learning (artificial intelligence).
Author: PEB
polyhedron
(definition)
Definition:
The set of solutions to a finite system of linear inequalities on real-valued variables. Equivalently, the intersection of a finite number of linear half-spaces in Rn.
Note:
From Algorithms and Theory of Computation Handbook, page 32-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
polylogarithmic
(definition)
Definition:
(1) Any function which is the sum of constants times powers of a logarithm of the argument: f(x)=Σi=0kcilogpi x. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a polylogarithmic function of the problem size, n. More formally m(n) = O(logk n).
Author: PEB
polynomial
(definition)
Definition:
(1) Any function which is the sum of constants times powers of the argument: f(x)=Σi=0k cixpi. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a polynomial function of the problem size, n. More formally m(n) = O(nk).
Note:
Strictly speaking, a linear function is a polynomial with the highest exponent being 1, and a logarithmic function is a polynomial with fractional exponents. However polynomial usually means exponents greater than 1.
Author: PEB
More information
An explanation of how quadratic and other polynomials got their names.
polynomial approximation scheme
(algorithmic technique)
Definition:
A set of algorithms {Aε| ε > 0}, where each Aε is a (1+ε)-approximation algorithm and the execution time is bounded by a polynomial in the length of the input. The execution time may depend on the choice of ε. Sometimes referred to more precisely as polynomial-time approximation scheme.
Also known as PTAS.
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
polynomial hierarchy
(definition)
Definition:
The classes of languages accepted by k-alternating Turing machines, over all k≥ 0 and with initial state existential or universal. The bottom level (k=0) is the class P. The next level (k=1) comprises NP and co- NP.
Note:
From Algorithms and Theory of Computation Handbook, page 29-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
polynomial time
(definition)
Definition:
When the execution time of a computation, m(n), is no more than a polynomial function of the problem size, n. More formally m(n) = O(nk) where k is a constant.
Specialization (... is a kind of me.)
sublinear time algorithm.
Note:
Broadly speaking, polynomial time algorithms are reasonable to compute. The time to run exponential algorithms grows too fast to expect to be able to compute exact solutions in all cases.
Author: PEB
polynomial-time reduction
(definition)
Definition:
A transformation of one problem into another which is computable in polynomial time.
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
polyphase merge
(algorithm)
Definition:
A nonbalanced k-way merge which reduces the number of output files needed by reusing the emptied input file or device as one of the output devices. This is most efficient if the number of output runs in each output file is different.
Author: ASK
polyphase merge sort
(algorithm)
Definition:
A merge sort algorithm that reduces the number of intermediate files needed by reusing emptied files.
Author: ASK
polytope
(definition)
Definition:
A closed, bounded N-dimensional figure whose faces are hyperplanes. Informally, a multidimensional solid with flat sides. A generalization of polyhedron.
Specialization (... is a kind of me.)
simplex.
Aggregate parent (I am a part of or used in ...)
P-tree.
Author: PEB
poset
(definition)
Definition:
A set the elements of which are subject to a partial order.
Also known as partially ordered set.
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
postman's sort
(algorithm)
Definition:
A highly engineered variant of top-down radix sort where attributes of the key are described so the algorithm can allocate buckets and distribute efficiently.
Generalization (I am a kind of ...)
top-down radix sort.
Note:
This is the algorithm used by letter-sorting machines in the post office: first states, then post offices, then routes, etc. Since keys are not compared against each other, sorting time is O(cn), where c depends on the size of the key and number of buckets. You probably used a form of this if you sorted lots of papers alphabetically: you put each paper in its pile (or bucket), A's, B's, C's, D's, etc., then sort each pile. This is similar to radix sort, but works "top down" or "most significant digit first" while radix sort works "bottom up" or "least significant digit first". Also this does not merge distributed items while radix sort does.
After Robert Ramey (ramey@rrsd.com)
Author: PEB
More information
Robert Ramey's August 1992 article.
Robert Ramey, The Postman's Sort, C Users Journal, August 1992.
postorder traversal
(algorithm)
Definition:
Process all nodes of a tree by recursively processing all subtrees, then finally processing the root.
Also known as postfix traversal.
Generalization (I am a kind of ...)
tree traversal, depth-first search.
Note:
For instance, if the "processing" is just printing, a tree is printed as "(first subtree) (second subtree) ... (last subtree) root." Here is pseudocode for a binary tree:
postorder(tree)
begin
if tree is null, return;
postorder(tree.left_subtree);
postorder(tree.right_subtree);
print(tree.root);
end
Author: PEB
Post's correspondence problem
(classic problem)
Definition:
Given a set of pairs of strings, find a sequence of pairs such that the concatenation of all first members of the pairs is the same string as the concatenation of all second members. This is an undecidable problem.
Also known as PCP.
Author: SKS
More information
Emil Post, A Variant of a Recursively Unsolvable Problem. Bulletin of the American Mathematical Society, 52:264-268, 1946.
potential function
(definition)
Definition:
A measure of a data structure whose change after an operation corresponds to the time cost of the operation.
Note:
If an inexpensive operation results in an increase of the potential function, but the increase of the potential function is within a constant factor of the actual cost of the operation, the amortized cost of the operation is unchanged. Meanwhile, if an expensive operation results in a decrease of the potential function that offsets the cost of the expensive operation, the amortized cost of the expensive operation may be small. For such an analysis to remain valid, the potential function must stay nonnegative, and begin with a value of zero. For more on amortized analysis and its origins see Tarjan.
Author: CLK
More information
R. E. Tarjan, Amortized computational complexity, SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1985.
predicate
(definition)
Definition:
A function that returns true or false. Conceptually it tests for a condition.
Note:
See the description of isEmpty() in the Notes for abstract data type.
Author: PEB
prefix
(definition)
Definition:
The beginning characters of a string. More formally a string v∈Σ* is a prefix of a string u∈Σ* if u=vu' for some string u'∈Σ*.
Note:
From Algorithms and Theory of Computation Handbook, pages 11-26 and 12-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
prefix code
(definition)
Definition:
Set of words such that no word of the set is a prefix of another word in the set. A prefix code may be represented by a coding tree.
Note:
From Algorithms and Theory of Computation Handbook, page 12-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
preorder traversal
(algorithm)
Definition:
Process all nodes of a tree by processing the root, then recursively processing all subtrees.
Also known as prefix traversal.
Generalization (I am a kind of ...)
tree traversal, depth-first search.
Note:
For instance, if the "processing" is just printing, a tree is printed as "root (first subtree) (second subtree) ... (last subtree)." Here is pseudocode for a binary tree:
preorder(tree)
begin
if tree is null, return;
print(tree.root);
preorder(tree.left_subtree);
preorder(tree.right_subtree);
end
Author: PEB
primary clustering
(definition)
Definition:
The tendency for some collision resolution schemes to create long runs of filled slots near the hash function position of keys.
Note:
Primary clustering increases average search time. Linear probing is especially susceptible to primary clustering. Clustering may be minimized with double hashing.
Author: PEB
primitive recursive
(definition)
Definition:
A total function which can be written using only nested conditional (if-then-else) statements and fixed iteration (for) loops.
Note:Ackermann's function is computable, but is not primitive recursive. Primitive recursion functions always terminate. More powerful languages have some functions which cannot be proved to either terminate or run forever.
After Algorithms and Theory of Computation Handbook, footnote, page 26-13, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: PEB
Prim-Jarnik algorithm
(algorithm)
Definition:
Compute a minimum spanning tree by beginning with any vertex as the current tree. At each step add a least edge between any vertex not in the tree and any vertex in the tree. Continue until all vertices have been added.
Aggregate child (... is a part of or used in me.)
greedy algorithm.
Author: JLG
More information
Eppstein's lecture outlining and contrasting MST algorithms.
V. Jarník, O jistem problemu minimalnim, Praca Moravske Prirodovedecke Spolecnosti, 6:57-63, 1930. (in Czech)
R. C. Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J., 36:1389-1401, 1957.
principle of optimality
(definition)
Definition:
In some optimization problems, components of a globally optimal solution are themselves globally optimal.
Note:
From Algorithms and Theory of Computation Handbook, page 1-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
priority queue
(data structure)
Definition:
An abstract data type to efficiently support finding the item with the highest priority across a series of operations. The basic operations are: insert, find-minimum (or maximum), and delete-minimum (or maximum). Some implementations also efficiently support join two priority queues (meld), delete an arbitrary item, and increase the priority of a item (decrease-key).
Formal Definition: The operations new(), insert(v, PQ), find-minimum or min(PQ), and delete-minimum or dm(PQ) may be defined with axiomatic semantics as follows.
- new() returns a priority queue
- min(insert(v, new())) = v
- dm(insert(v, new())) = new()
- min(insert(v, insert(w, PQ))) = if priority(v) < priority(min(insert(w, PQ))) then v else min(insert(w, PQ))
- dm(insert(v, insert(w, PQ))) = if priority(v) < priority(min(insert(w, PQ))) then insert(w, PQ) else insert(v, dm(insert(w, PQ)))
where PQ is a priority queue, v and w are items, and priority(v) is the priority of item v.
Generalization (I am a kind of ...)
abstract data type.
Specialization (... is a kind of me.)
pagoda, leftist tree, van Emde-Boas priority queue.
Aggregate parent (I am a part of or used in ...)
best-first search, Dijkstra's algorithm.
Aggregate child (... is a part of or used in me.)
heap, Fibonacci heap.
Note:
It can be implemented efficiently with a heap. After LK.
Author: PEB
prisoner's dilemma
(classic problem)
Definition:
Two prisoners are questioned separately about a crime they committed. Each may give evidence against the other or may say nothing. If both say nothing, they get a minor reprimand and go free because of lack of evidence. If one gives evidence and the other says nothing, the first goes free and the second is severely punished. If both give evidence, both are severely punished. The overall (globally) best strategy is for both to say nothing. However not knowing (or trusting) what the other will do, each prisoner's (locally) best strategy is to give evidence, which is the worst possible outcome. In general, a situation where local optimization leads to the worst possible outcome globally.
Note:
This problem is in the area of game theory.
Author: PEB
More information
A thorough treatment from Principia Cybernetica including links to a web-based game and related entries and definitions.
probabilistic algorithm
(definition)
Definition:
Any algorithm that works for all practical purposes but has a theoretical chance of being wrong.
Specialization (... is a kind of me.)
Bloom filter, sublinear time algorithm.
Author: PEB
probabilistically checkable proof
(definition)
Definition:
An interactive proof system in which provers follow a fixed strategy, that is, one not affected by any messages from the verifier. The prover's strategy for a given instance x of a decision problem can be represented by a finite oracle language Bx, which constitutes a proof of the correct answer for x.
Note:
From Algorithms and Theory of Computation Handbook, page 29-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
probabilistic Turing machine
(definition)
Definition:
A Turing machine in which some transitions are random choices among finitely many alternatives.
Note:
The typical, deterministic Turing machine (TM) can be seen as a probabilistic TM with no more than one alternative for each transition. A nondeterministic TM is a probabilistic TM ignoring the probabilities.
From Algorithms and Theory of Computation Handbook, page 29-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
probe sequence
(definition)
Definition:
The list of locations which a method for open addressing produces as alternatives in case of a collision.
Author: PEB
procedure
(definition)
Definition:
A subroutine which does not return a value.
Author: PEB
process algebra
(definition)
Definition:
An algebraic theory to formalize the notion of concurrent computation, best exemplified in CSP and CCS.
Author: SKS
proper
(definition)
Definition:
(1) A subunit of a unit is not equal to the unit itself. For instance, a proper substring is not the whole string, a proper subset is not the whole set, a proper subgraph is not the whole graph, etc. (2) According to a rule, as in proper coloring.
Author: PEB
proper coloring
(definition)
Definition:
A vertex coloring or edge coloring of a graph in which no two adjacent vertices or edges have the same color.
Note:
Generally "coloring" is understood to mean "proper coloring".
Author: ME
proper subset
(definition)
Definition:
A set S2 is a proper subset of another set S1 if every element in S2 is in S1 and S1 has some elements which are not in S2.
Author: PEB
prune and search
(algorithmic technique)
Definition:
Find an optimal value by eliminating a constant fraction of remaining objects at each step. Eliminated objects are guaranteed not to affect the optimal value. A logarithmic number of steps reduces the number of objects to a constant, and a brute force approach can then solve it.
Also known as decimation.
Note:
Adapted from [AS98, page 422].
Author: PEB
pseudo-random number generator
(algorithm)
Definition:
A deterministic algorithm to generate a sequence of numbers with little or no discernible pattern in the numbers, except for broad statistical properties.
Also known as PRNG.
Specialization (... is a kind of me.)
linear congruential generator.
Note:
Any computer program is likely to generate pseudo-random numbers, not actually random numbers. This is important when, say, simulations are sensitive to subtle patterns in the "random" numbers used. Hardware-based random number generators are built from parts with naturally random events, such as noise in a diode. A generator may be "seeded", or initialized, with a random event, such as the current time in milliseconds, to give different sequences every time it is used. Do NOT use typical "random" number generators for security or cryptographic purposes. Random Numbers from David Wheeler's Secure Programming for Linux and Unix HOWTO, Section 11.3, gives suggestions and guidelines.
Author: PEB
More information
Random Number Generation and Testing with links to reports, standard tests, and on-going research. ent: a program to test the randomness of bytes in a file. Karl Entacher's thorough review and comparison of A collection of selected pseudorandom number generators with linear structures.
P-tree
(data structure)
Definition:
(1) A spatial access method that defines hyperplanes, in addition to the orthogonal dimensions, which node boundaries may parallel. Space is split by hierarchically nested polytopes (multidimensional boxes with nonrectangular sides). The R-tree is a special case that has no additional hyperplanes. (2) A spatial access method that splits space by hierarchically nested polytopes. The R-tree is a special case in which all polytopes are boxes.
Generalization (I am a kind of ...)
tree, spatial access method.
Specialization (... is a kind of me.)
R-tree.
Aggregate child (... is a part of or used in me.)
polytope.
Note:
(2) by Jagadish after [GG98].
Author: PEB
purely functional language
(definition)
Definition:
A language that does not allow any destructive operation---one which overwrites data---such as the assignment operation. Purely functional languages are free of side effects, i.e., invoking a function has no effect other than computing the value returned by the function.
Note:
From Algorithms and Theory of Computation Handbook, page 5-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
pushdown automaton
(definition)
Definition:
A restricted Turing machine where the tape acts as a pushdown store (or stack, where only the latest element can be read), with an extra one-way read-only input tape.
Also known as PDA.
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
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
|
