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 randomaccess 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
 Pcomplete
 PCP: see Post's correspondence problem
 PDA: see pushdown automaton
 Pearson's hash
 perfect binary tree
 perfect hashing
 perfect kary 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 straightline graph
 PLOPhashing
 point access method
 pointer jumping
 pointer machine
 poissonization
 polychotomy
 polyhedron
 polylogarithmic
 polynomial
 polynomial approximation scheme
 polynomial hierarchy
 polynomial time
 polynomialtime 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 randomaccess machine
 predicate
 prefix
 prefix code
 prefix computation
 prefix sums: see scan
 prefix traversal: see preorder traversal
 preorder traversal
 primary clustering
 primitive recursive
 PrimJarnik algorithm
 principle of optimality
 priority queue
 prisoner's dilemma
 PRNG: see pseudorandom 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
 pseudorandom number generator
 PTAS: see polynomial approximation scheme
 pth order Fibonacci numbers: see kth order Fibonacci numbers
 Ptree
 purely functional language
 pushdown automaton
 pushdown transducer
 pway merge sort: see kway 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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 3239, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 bottomup, 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 17. 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 4523, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
parallel prefix computation
(algorithm)
Definition:
Calculate an associative function, f, on all prefixes of an nelement 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[n2], s[n1])...)), using Θ(n) processors in Θ(log n) time. The algorithm is
for j := 0 to lg(n)1 do for i := 2^{j} to n1 paralleldo s[i] := f(s[i2^{j}], s[i]) where lg is the logarithm base 2, and paralleldo 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 writeafterread hazards in the paralleldo loop: old values of s[2^{j}] to s[n12^{j}] 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 randomaccess 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 473, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 822, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 524, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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:  ∀ s_{i} ∈ P, s_{i} ≠ ø
(no subset is empty),  ∀ s_{i}, s_{j} ∈ P, i ≠ j → s_{i} ∩ s_{j} = ø
(subsets are disjoint), and  U_{i=1} s_{i} = 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 4523, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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):514534, 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 1126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Pcomplete
(definition)
Definition:
A language L is Phard under NC manyone reducibility if L' ≤_{m}^{NC} for every L' ∈ P. A language L is Pcomplete under NC reducibility if L ∈ P and L is Phard.
Note:
From Algorithms and Theory of Computation Handbook, page 4523, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Pearson's hash
(algorithm)
Definition:
A hash function that uses an auxiliary array, but no shift or exclusiveor (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 orderpreserving minimal perfect hashing function.
Author: PEB
More information
Peter K. Pearson, Fast Hashing of VariableLength Text Strings, CACM, 33(6):677680, 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 2^{n+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, orderpreserving 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):738761, August 1994.
perfect kary tree
(definition)
Definition:
A kary 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 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
permutation
(algorithm)
Definition:
A rearrangement of elements, where none are lost, added, or changed. The FisherYates shuffle randomly permutes elements.
Also known as shuffle.
Generalization (I am a kind of ...)
combination.
Specialization (... is a kind of me.)
ideal random shuffle, FisherYates shuffle, JohnsonTrotter, 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 524, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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):86124, 1989.
phonetic coding
(classic problem)
Definition:
Code a string based on how it is pronounced.
Specialization (... is a kind of me.)
double metaphone, JaroWinkler, 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 2pass 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 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 straightline 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 4starts (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 923, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
planar straightline 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 1927, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
PLOPhashing
(data structure)
Definition:
Piecewise linear orderpreserving (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, hBtree, twin grid file, twolevel grid file, kd tree, BSPtree, quadtree, UBtree, buddy tree, localitysensitive 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 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 525, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1435, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 realvalued variables. Equivalently, the intersection of a finite number of linear halfspaces in R^{n}.
Note:
From Algorithms and Theory of Computation Handbook, page 3239, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
polylogarithmic
(definition)
Definition:
(1) Any function which is the sum of constants times powers of a logarithm of the argument: f(x)=Σ_{i=0}^{k}c_{i}log^{pi} 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(log^{k} n).
Author: PEB
polynomial
(definition)
Definition:
(1) Any function which is the sum of constants times powers of the argument: f(x)=Σ_{i=0}^{k} c_{i}x^{pi}. (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(n^{k}).
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 polynomialtime approximation scheme.
Also known as PTAS.
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
polynomial hierarchy
(definition)
Definition:
The classes of languages accepted by kalternating 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 2920, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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(n^{k}) 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
polynomialtime 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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
polyphase merge
(algorithm)
Definition:
A nonbalanced kway 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 Ndimensional 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 ...)
Ptree.
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
postman's sort
(algorithm)
Definition:
A highly engineered variant of topdown radix sort where attributes of the key are described so the algorithm can allocate buckets and distribute efficiently.
Generalization (I am a kind of ...)
topdown radix sort.
Note:
This is the algorithm used by lettersorting 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, depthfirst 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:264268, 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):306318, 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 1126 and 1221, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1221, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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, depthfirst 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 (ifthenelse) 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 2613, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: PEB
PrimJarnik 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:5763, 1930. (in Czech) R. C. Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J., 36:13891401, 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 126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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, findminimum (or maximum), and deleteminimum (or maximum). Some implementations also efficiently support join two priority queues (meld), delete an arbitrary item, and increase the priority of a item (decreasekey).
Formal Definition: The operations new(), insert(v, PQ), findminimum or min(PQ), and deleteminimum 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 EmdeBoas priority queue.
Aggregate parent (I am a part of or used in ...)
bestfirst 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 webbased 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 B_{x}, which constitutes a proof of the correct answer for x.
Note:
From Algorithms and Theory of Computation Handbook, page 2920, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2920, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 S_{2} is a proper subset of another set S_{1} if every element in S_{2} is in S_{1} and S_{1} has some elements which are not in S_{2}.
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
pseudorandom 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 pseudorandom numbers, not actually random numbers. This is important when, say, simulations are sensitive to subtle patterns in the "random" numbers used. Hardwarebased 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 ongoing 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.
Ptree
(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 Rtree is a special case that has no additional hyperplanes. (2) A spatial access method that splits space by hierarchically nested polytopes. The Rtree 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.)
Rtree.
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 operationone which overwrites datasuch 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 524, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 oneway readonly input tape.
Also known as PDA.
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
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
