Analysis of Algorithms : An Active Learning Approach

INDEX 293

Pivot element
and quicksort, 89
PivotList function, 90, 91, 92
relationship between indices and element
values in, 90
splitting the list, 90-91
PivotPoint, 9 2
PivotValue, 9 1
Pixels, 106, 107
Polynomial calculations, 107-111
Horner’s method, 108
preprocessed coefficients, 108-111
Polynomial equations, 106, 107, 214
Polynomial of degree 7
work done for, 111
Polynomial of degree N, work done for, 111
Polynomials, 106
Polynomial time, 218, 224, 228
algorithms, 217, 232
complexity, 215
problems, 220
PolyphaseMerge, 9 8
position variable, 257
Power series expansions, 106
PRAM. See Parallel random access machine
PRAM model, 183-185
Preprocessed coefficients, 108-111, 270, 271
Preprocessing steps, 188, 189
Prim, R. C., 155
Prime numbers, 180n1
and Monte Carlo algorithm, 246
Probabilistic algorithms, 232
comparisons of, 250
Las Vegas, 232, 246-249
Monte Carlo, 232, 244-246

Sherwood, 232, 249-250

Probabilistic counting, 243-244

Probabilities, 15-16

Problem reductions, 217-218

Problems

backpack, 222

bin packing, 221-222

CNF-satisfiability, 222-223

graph coloring, 220-221, 228

job scheduling, 223, 227

NP, 220-223

NP-complete, 218-220

reducing, 217-218

subset sum, 222

Procedures, 38

Processor communication, 181-182

Programming

dynamic, 138, 252-257

Program profiling tools, 39

Programs analysis, 38-39

Pseudocode, 7

Pseudorandom number generation, 261-264

example application, 262-264

generating numbers in different range,

262

Pushing/popping graph vertices, 151

Q

Queue

BreadthFirstTraversal, 152

Quicksort, 58, 59, 89-93, 91, 92, 96, 197

average-case analysis of, 91-93

chapter study suggestion results, 269

pivot element for, 249