INDEX684
Pairing, 100
pairwise disjoint, 110
pairwise independence, 627
pairwise independent, 554 , 556, 628,
631
Pairwise Independent Additivity, 628
Pairwise Independent Sampling, 632,
654
parallel schedule, 254
parallel time, 255
parity, 149
partial correctness, 131
partial correctness assertion, 395
partial functions, 72
partition, 257 , 307
Pascal’s Identity, 477
path, 608
path relation, 242
path-total, 259
perfect graph, 310
perfect number, 184, 217
permutation, 206 , 384 , 456 , 494
Perturbation Method, 403
pessimal spouse, 317
Pick-4, 637
pigeonhole principle, 399
planar drawing, 361
planar embedding, 368 , 382
planar embeddings, 368
planar graph, 365
planar graphs, 323
planar subgraph, 374
pointwise, 73
Polyhedra, 377
polyhedron, 378
polynomial growth, 49
polynomial time, 307
population size, 633
positive path relation, 242
potential, 154
power set, 69 , 79, 94
Power Set axiom, 100
Power sets, 94
precondition, 395
predicate, 9
pre-MST, 335
preserved, 202
preserved invariant, 127
preserved under isomorphism, 306
Primality Testing, 185
prime, 7 , 184
prime factorization, 217
Prime Factorization Theorem, 28
prime number, 184
Prime Number Theorem, 210
probability density function, 576
probability density function (pdf), 576
probability function, 533 , 564
probability of an event, 533
probability space, 533
product of sets, 71
Product Rule, 450 , 541
proof, 10
proof by contradiction, 18
proper subset, 310
proposition, 4 , 7
propositional variables, 36
public key, 209
public key cryptography, 209
Pulverizer, 217, 221
Pythagoreans, 377quicksort, 582
quotient, 187Rabin cryptosystem, 226
randomized, 513
randomized algorithm, 582
random variable, 573