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