Mathematics for Computer Science

INDEX908

page rank, 850 , 852
pair, 236
pairwise independence, 799
pairwise independent, 719 , 800, 803
Pairwise Independent Additivity, 800
Pairwise Independent Sampling, 804,
827
partial correctness, 139
partial fractions, 635
partial order, 335, 362
strict, 336 , 344
weak, 337 , 344
particular solution, 879
partition, 333 , 401
Pascal’s Triangle Identity, 589
path, 775
perfect graph, 404
perfect number, 244, 283
permutation, 498 , 558
Perturbation Method, 505
perturbation method, 628
pessimal spouse, 412
Pick-4, 810
planar drawing, 473
planar embedding, 479 , 480 , 496
planar graph, 477
planar graphs, 417
planar subgraph, 487
plug-and-chug, 865
pointwise, 88
Polyhedra, 489
polyhedron, 489
polynomial time, 56 , 254, 401
population size, 806
predicate, 8
pre-MST, 430
preserved invariant,seeinvariant
preserved under isomorphism, 400
prime, 5, 26, 254

Prime Number Theorem, 255, 275

relatively prime, 271

Prime Factorization Theorem,seeUnique

Factorization Theorem

probability density function, 743

probability density function,, 742

probability function, 686 , 727

probability of an event, 686

probability space, 686

Product Rule, 703

product rule, 737

Product Rule (counting), 553

Product Rule (generating functions),

630

proof, 9 , 17

proof by contradiction, 16

proposition, 4 , 5

propositional variable, 42

public key cryptography, 279

Pulverizer, 251 , 284, 285

Pvs.NP, 56

Pythagoreans, 489

quicksort, 749

quotient, 246

randomized algorithm, 749

random sample, 830

random sampling, 829

random variable, 739

random variables, 740

random walk, 775, 851

Random Walks, 839

range, 88

reachable, 135

reciprocal, 645

recurrence, 865

recursive data type, 173

ambiguity, 179

reflexive relation, 336, 343