P

| < Day Day Up > |

# Index

### P

P (complexity class), 967, 973, 977, 979 ex.
package wrapping, 955
page on a disk, 436, 452 pr.
paging, 22
pair, ordered, 1073
pairwise disjoint sets, 1073
pairwise independence, 1103
pairwise relatively prime, 854
Pan's method for matrix multiplication, 741 ex.
parallel-machine-scheduling problem, 1051 pr.
parameter, 20
costs of passing, 85 pr.
parent, 1087
in a breadth-first tree, 532
PARENT, 128
parenthesis structure of depth-first search, 543
parenthesis theorem, 543
parenthesization of a matrix-chain product, 331
parse tree, 999
partial order, 1076
PARTITION, 146
partitioning algorithm, 146- 148
around median of 3 elements, 159 ex.
randomized, 154
partition of a set, 1073, 1076
Pascal's triangle, 1099 ex.
path, 1081
augmenting, 654, 696 pr.
critical, 594
find, 506
hamiltonian, 983 ex.
longest, 342, 966
shortest, see shortest paths
weight of, 580
PATH, 969, 976
path compression, 506
path cover, 692 pr.
path length, of a tree, 270 pr., 1091 ex.
path-relaxation property, 587, 609- 610
pattern in string matching, 906
nonoverlappable, 922 ex.
pattern matching, see string matching
penalty, 399
perfect hashing, 245- 249
perfect matching, 669 ex.
permutation, 1079
bit-reversal, 425 pr., 841
Josephus, 318 pr.
in place, 102
random, 101- 104
of a set, 1095
uniform random, 93, 101
permutation matrix, 728, 733 ex.
LUP decomposition of, 754 ex.
permutation network, 722 pr.
PERMUTE-BY-CYCLIC, 105 ex.
PERMUTE-BY-SORTING, 101
PERMUTE-WITH-ALL, 105 ex.
PERMUTE-WITHOUT-IDENTITY, 104 ex.
persistent data structure, 294 pr., 432
PERSISTENT-TREE-INSERT, 294 pr.
PERT chart, 594, 594 ex.
phi function, 865
PISANO-DELETE, 496 pr.
pivot
in linear programming, 793- 796, 803 ex.
in LU decomposition, 749
in quicksort, 146
PIVOT, 795
platter, 435
pointer, 20
array implementation of, 209- 213
point-value representation, 825
polar angle, 939 ex.
Pollard's rho heuristic, 897- 901, 901 ex.
POLLARD-RHO, 897
polygon, 939 ex.
kernel of, 956 ex.
star-shaped, 956 ex.
polylogarithmically bounded, 54
polynomial, 52, 822
addition of, 822
asymptotic behavior of, 57 pr.
coefficient representation of, 824
evaluation of, 39 pr., 824, 829 ex., 845- 846 pr.
interpolation by, 825, 830 ex.
multiplication of, 823, 827- 829, 844 pr.
point-value representation of, 825
polynomially bounded, 52
polynomially related, 974
polynomial-time acceptance, 976
polynomial-time algorithm, 850, 966
polynomial-time approximation scheme, 1023
polynomial-time computability, 974
polynomial-time decision, 976
polynomial-time reducibility (≤P), 984, 994 ex.
polynomial-time solvability, 973
polynomial-time verification, 979- 983
pop
from a run-time stack, 162 pr.
stack operation, 201
POP, 201
positional tree, 1090
positive-definite matrix, 732
positive flow, 645
post-office location problem, 194 pr.
postorder tree walk, 254
potential function, 413
for lower bounds, 429
potential method, 412- 416
for binary counters, 414- 415
for disjoint-set data structures, 512- 517
for dynamic tables, 419- 420, 422- 424
for Fibonacci heaps, 479- 482, 487- 488, 491- 492
for the generic push-relabel algorithm, 678- 679
for the Knuth-Morris-Pratt algorithm, 926- 927
for min-heaps, 416 ex.
for restructuring red-black trees, 428 pr.
for stack operations, 413- 414
potential of a data structure, 413
power
of an element, modulo n, 876- 881
kth, 855 ex.
nontrivial, 855 ex.
power series, 86 pr.
power set, 1073
Pr {} (probability distribution), 1100
predecessor
in binary search trees, 258- 259
in breadth-first trees, 532
in B-trees, 447 ex.
in linked lists, 204
in order-statistic trees, 310 ex.
in red-black trees, 276
in shortest-paths trees, 584
PREDECESSOR, 198
predecessor matrix, 621
predecessor subgraph
in all-pairs shortest paths, 621
in breadth-first search, 537
in depth-first search, 540
in single-source shortest paths, 584
predecessor-subgraph property, 587, 612- 613
preemption, 402 pr.
prefix
of a sequence, 351
of a string (⊏), 907
prefix code, 385
prefix function, 923- 925
prefix-function iteration lemma, 927
preflow, 669
preorder tree walk, 254
presorting, 961
Prim's algorithm, 570- 573
with an adjacency matrix, 573 ex.
in approximation algorithm for traveling-salesman problem, 1028
implemented with a Fibonacci heap, 573
implemented with a min-heap, 573
with integer edge weights, 574 ex.
similarity to Dijkstra's algorithm, 570, 599
for sparse graphs, 575 pr.
primality testing, 887- 896, 904
Miller-Rabin test, 890- 896
pseudoprimality testing, 889- 890
primal linear program, 805
primary clustering, 239
primary memory, 434
prime distribution function, 888
prime number, 851
density of, 887- 888
prime number theorem, 888
primitive root of , 877
principal root of unity, 831
principle of inclusion and exclusion, 1074 ex.
PRINT-ALL-PAIRS-SHORTEST-PATH, 621
PRINT-INTERSECTING-SEGMENTS, 946 ex.
PRINT-LCS, 355
PRINT-OPTIMAL-PARENS, 338, 338 ex.
PRINT-PATH, 538
PRINT-STATIONS, 330
priority queue, 138- 142
in constructing Huffman codes, 387
in Dijkstra's algorithm, 598
heap implementation of, 138- 142
max-priority queue, 138
min-priority queue, 138, 141 ex.
with monotone extractions, 144
in Prim's algorithm, 572- 573
see also binary search tree, binomial heap,
Fibonacci heap
probabilistic analysis, 92- 93, 106- 117
of approximation algorithm for MAX-3-CNF satisfiability, 1040
of average-case lower bound for sorting, 178 pr.
and average inputs, 26
of average node depth in a randomly built binary search tree, 270 pr.
of balls and bins, 109- 110
of birthday paradox, 106- 109
of bucket sort, 174- 177, 177 ex.
of collisions, 228 ex., 249 ex.
of convex hull over a sparse-hulled
distribution, 964 pr.
of file comparison, 915 ex.
of hashing with chaining, 226- 228
of the height of a randomly built binary search tree, 265- 268
of the hiring problem, 97- 98
of insertion into a binary search tree with equal keys, 268 pr.
of longest-probe bound for hashing, 249 pr.
of the Miller-Rabin primality test, 893- 896
of open-address hashing, 241- 244, 244 ex.
of partitioning, 153 ex., 159 ex., 160 pr., 162 pr.
of perfect hashing, 246- 249
of Pollard's rho heuristic, 898- 901
of probabilistic counting, 118 pr.
of quicksort, 156- 158, 160 pr., 162 pr., 268 ex.
of the Rabin-Karp algorithm, 915
and randomized algorithms, 99- 101
of randomized selection, 186- 189
of searching a compact list, 218 pr.
of slot-size bound for chaining, 250 pr.
of sorting points by distance from origin, 177 ex.
of streaks, 110- 114
of universal hashing, 233- 236
probabilistic counting, 118 pr.
probability, 1100- 1106
probability density function, 1107
probability distribution, 1100
probability distribution function, 177 ex.
probe, 237, 249 pr.
probe sequence, 237
probing, see linear probing, quadratic probing
problem
abstract, 972
computational, 5- 6
concrete, 973
decision, 969, 972
intractable, 966
optimization, 323, 968, 972
solution to, 6, 972- 973
tractable, 966
procedure, 6, 15- 16
product
Cartesian, 1074
cross, 934
inner, 730
of matrices, 729, 734 ex.
outer, 730
of polynomials, 823
rule of, 1095
scalar flow, 650 ex.
professional wrestler, 539 ex.
program counter, 990
programming, see dynamic programming, linear programming
proper ancestor, 1087
proper descendant, 1087
proper subgroup, 866
proper subset (⊂), 1071
prune-and-search method, 948
pruning a Fibonacci heap, 497 pr.
pseudocode, 15, 19- 20
pseudoinverse, 764
pseudoprime, 889- 890
PSEUDOPRIME, 889
pseudorandom-number generator, 94
public key, 881, 884
public-key cryptosystem, 881- 887
PUSH
push-relabel operation, 672
stack operation, 201
push onto a run-time stack, 162 pr.
push operation (in push-relabel algorithms), 671- 672
push-relabel algorithm, 669- 692
basic operations in, 671- 673
by discharging an overflowing vertex of maximum height, 691 ex.
to find a maximum bipartite matching, 680 ex.
gap heuristic for, 691 ex.
generic algorithm, 673- 681
with a queue of overflowing vertices, 691 ex.
relabel-to-front algorithm, 681- 692

| < Day Day Up > |