# Index
### <a>P</a>
*P*, sets of, [386-390](LiB0077.html#905)
Papadimitriou, C.H., [406](LiB0077.html#956)
Parallel algorithms, [42](LiB0012.html#130). *See also specific parallel algorithms*
Parallel architectures, [488-494](LiB0089.html#1231)
address-space organization, [490](LiB0090.html#1236)
control mechanism, [488-490](LiB0089.html#1231)
exercises, [508-509](LiB0091.html#1275)
interconnection networks, [491-494](LiB0090.html#1243)
**Parallel Binomial Coefficient,** [501-503](LiB0091.html#1262)
Parallel computer, [485-486](LiB0089.html#1226)
Parallel computers, [488](LiB0089.html#1231). *See also* [Parallel architectures](#parallelarchitectures)
**Parallel CRCW Find Largest Key,** [506-507](LiB0091.html#1271)
**Parallel Find Largest Key,** [499-501](LiB0091.html#1259)
**Parallel Mergesort,** [503-505](LiB0091.html#1265)
algorithm, [503-504](LiB0091.html#1265)
worst-case time complexity, [505](LiB0091.html#1269)
Parallel random access machine (PRAM), [495](LiB0091.html#1253). *See also* [PRAM model](#prammodel)
Parallel sorting, [503-505](LiB0091.html#1265)
Parameters, [3](LiB0008.html#21)
Partition, [284](LiB0056.html#666), [358](LiB0072.html#847)
**Partition**, [62-63](LiB0018.html#180)
Pascal's triangle, [94-95](LiB0025.html#259), [111](LiB0028.html#296), [501-502](LiB0091.html#1262)
Patashnik, O., [441](LiB0083.html#1077)
Paterson, M., [366](LiB0072.html#861)
Path, [97](LiB0026.html#266)
Path compression, [598](LiB0108.html#1482)
Pearl, J., [256](LiB0050.html#607), [406](LiB0077.html#956), [487](LiB0089.html#1229)
Permutations, [275-276](LiB0053.html#646), [533](LiB0100.html#1333)
Pippenger, N., [366](LiB0072.html#861)
Pivotitem, [65](LiB0018.html#187)
Pivotpoint, [64](LiB0018.html#186), [65](LiB0018.html#187), [358](LiB0072.html#847)
Planar graph, [210](LiB0043.html#522)
**Polynomial Determine Prime,** [464-474](LiB0086.html#1166)
Polynomial-time algorithms, [376](LiB0074.html#882), [382](LiB0075.html#891), [386](LiB0077.html#905)
Polynomial-time many-one reducible, [393](LiB0077.html#920)
Polynomial-time nondeterministic algorithms, [389](LiB0077.html#910)
Polynomial-time reducibility, [392](LiB0077.html#917)
Polynomial-time Turing reducible, [402](LiB0077.html#948), [405](LiB0077.html#955)
Population
probability and, [531](LiB0100.html#1328)
at random from, [539](LiB0100.html#1346)
PRAM (parallel random access machine), [495](LiB0091.html#1253)
PRAM Model, [488](LiB0089.html#1231), [495](LiB0091.html#1253)
CRCW algorithms, [505-508](LiB0091.html#1269)
CREW (concurrent-read, exclusive write), [496-501](LiB0091.html#1254)
dynamic programming applications, [501-505](LiB0091.html#1262)
Pratt, V., [366](LiB0072.html#861)
Prefix codes, [170](LiB0036.html#430)
Preorder, [188](LiB0039.html#473)
Presburger Arithmetic, [383](LiB0076.html#895), [398](LiB0077.html#933)
Prim, R.C., [156](LiB0033.html#398)
Prime-checking algorithm, [381](LiB0075.html#890)
Prime distribution function (蟺*(n)*), [457](LiB0086.html#1140)
Prime factorization, [424-426](LiB0081.html#1011)
Prime numbers
definition of, [420-421](LiB0080.html#992)
large, finding, [456-476](LiB0085.html#1137)
Prime number theorem, [457](LiB0086.html#1140)
Primes problem, [400](LiB0077.html#940), [401](LiB0077.html#945)
**Prim's Algorithm,** [144-148](LiB0033.html#372)
every-case time complexity, [148-150](LiB0033.html#379)
theorem, [149-150](LiB0033.html#382)
*vs.* Kruskal's Algorithm, [155-156](LiB0033.html#394)
Principle of Indifference, [532-534](LiB0100.html#1330), [540](LiB0100.html#1348)
Principle of Optimality, [106](LiB0027.html#286)
**Print Optimal Order,** [115](LiB0028.html#305)
**Print Shortest Path,** [104-105](LiB0026.html#281)
Priority cue, [172-174](LiB0036.html#437)
Priority write protocol, [506](LiB0091.html#1271)
Probabilistic algorithms, [200-201](LiB0040.html#499)
**Probabilistic Selection**
algorithm, [368](LiB0072.html#865)
expected-value time complexity, [369-370](LiB0072.html#866)
Probability, [256](LiB0050.html#607), [531-542](LiB0100.html#1328)
conditional, [256](LiB0050.html#607)
expected value, [540-542](LiB0100.html#1348)
Principle of Indifference and, [532-534](LiB0100.html#1330)
randomness and, [536-540](LiB0100.html#1339)
relative frequency appraoch, [533-534](LiB0100.html#1333)
subjectivistic approach, [534-535](LiB0100.html#1335)
Probability function, [531](LiB0100.html#1328)
Probability space, definition of, [532](LiB0100.html#1330)
Problems. *See also specific problems*
definition of, [2](LiB0008.html#18)
example of, [2](LiB0008.html#18)
Problem-solving techniques, [1-2](LiB0008.html#17), *See also* [Algorithms](LiB0110.html#1487); *specific algorithms*
Procedure, [6](LiB0008.html#29)
Process, [24](LiB0010.html#73)
Processor, [486](LiB0089.html#1227)
Profit, [218-225](LiB0045.html#539)
Promising function, [192](LiB0039.html#481)
Promising node, [191](LiB0039.html#479), [234](LiB0047.html#568)
Promising subset, [148-149](LiB0033.html#379)
Proof of contradiction, [34](LiB0011.html#106)
Proper subset, [527](LiB0098.html#1321)
Pruned state space tree, [191](LiB0039.html#479)
Pruning, [191](LiB0039.html#479)
Pseudocode, [4](LiB0008.html#25), [6](LiB0008.html#29)
Pseudopolynomial-time algorithm, [382](LiB0075.html#891)
Public key, [476](LiB0086.html#1199)
Public-key cryptosystems
definition of, [476-477](LiB0086.html#1199)
RSA public-key cryptosystem, [478-480](LiB0087.html#1207)
Pure quadratic functions, [25-26](LiB0010.html#75)
- Table of Contents
- BackCover
- Foundations of Algorithms Using C++ Pseudocode, Third Edition
- Preface
- Chapter Contents
- Pedagogy
- Course Outlines
- Acknowledgments
- Errors
- Chapter 1: Algorithms - Efficiency, Analysis, and Order
- 1.2 The Importance of Developing Efficient Algorithms
- 1.3 Analysis of Algorithms
- 1.4 Order
- 1.5 Outline of This Book
- Exercises
- Chapter 2: Divide-and-Conquer
- 2.1 Binary Search
- 2.2 Mergesort
- 2.3 The Divide-and-Conquer Approach
- 2.4 Quicksort (Partition Exchange Sort)
- 2.5 Strassen's Matrix Multiplication Algorithm
- 2.6 Arithmetic with Large Integers
- 2.7 Determining Thresholds
- 2.8 When Not to Use Divide-and-Conquer
- Exercises
- Chapter 3: Dynamic Programming
- 3.1 The Binomial Coefficient
- 3.2 Floyd's Algorithm for Shortest Paths
- 3.3 Dynamic Programming and Optimization Problems
- 3.4 Chained Matrix Multiplication
- 3.5 Optimal Binary Search Trees
- 3.6 The Traveling Salesperson Problem
- Exercises
- Chapter 4: The Greedy Approach
- 4.1 Minimum Spanning Trees
- 4.2 Dijkstra's Algorithm for Single-Source Shortest Paths
- 4.3 Scheduling
- 4.4 Huffman Code
- 4.5 The Greedy Approach versus Dynamic Programming: The Knapsack Problem
- Exercises
- Chapter 5: Backtracking
- 5.2 The n-Queens Problem
- 5.3 Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm
- 5.4 The Sum-of-Subsets Problem
- 5.5 Graph Coloring
- 5.6 The Hamiltonian Circuits Problem
- 5.7 The 0-1 Knapsack Problem
- Exercises
- Chapter 6: Branch-and-Bound
- 6.1 Illustrating Branch-and-Bound with the 0 - 1 Knapsack problem
- 6.2 The Traveling Salesperson Problem
- 6.3 Abductive Inference (Diagnosis)
- Exercises
- Chapter 7: Introduction to Computational Complexity - The Sorting Problem
- 7.2 Insertion Sort and Selection Sort
- 7.3 Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison
- 7.4 Mergesort Revisited
- 7.5 Quicksort Revisited
- 7.6 Heapsort
- 7.6.1 Heaps and Basic Heap Routines
- 7.6.2 An Implementation of Heapsort
- 7.7 Comparison of Mergesort, Quicksort, and Heapsort
- 7.8 Lower Bounds for Sorting Only by Comparison of Keys
- 7.8.1 Decision Trees for Sorting Algorithms
- 7.8.2 Lower Bounds for Worst-Case Behavior
- 7.8.3 Lower Bounds for Average-Case Behavior
- 7.9 Sorting by Distribution (Radix Sort)
- Exercises
- Chapter 8: More Computational Complexity - The Searching Problem
- 8.1 Lower Bounds for Searching Only by Comparisons of Keys
- 8.2 Interpolation Search
- 8.3 Searching in Trees
- 8.4 Hashing
- 8.5 The Selection Problem: Introduction to Adversary Arguments
- Exercises
- Chapter 9: Computational Complexity and Interactability - An Introduction to the Theory of NP
- 9.2 Input Size Revisited
- 9.3 The Three General Problem Categories
- 9.4 The Theory of NP
- 9.5 Handling NP-Hard Problems
- Exercises
- Chapter 10: Number-Theoretic Algorithms
- 10.1 Number Theory Review
- 10.2 Computing the Greatest Common Divisor
- 10.3 Modular Arithmetic Review
- 10.4 Solving Modular Linear Equations
- 10.5 Computing Modular Powers
- 10.6 Finding Large Prime Numbers
- 10.7 The RSA Public-Key Cryptosystem
- Exercises
- Chapter 11: Introduction to Parallel Algorithms
- 11.1 Parallel Architectures
- 11.2 The PRAM Model
- Exercises
- Appendix A: Review of Necessary Mathematics
- A.2 Functions
- A.3 Mathematical Induction
- A.4 Theorems and Lemmas
- A.5 Logarithms
- A.6 Sets
- A.7 Permutations and Combinations
- A.8 Probability
- Exercises
- Appendix B: Solving Recurrence Equations - With Applications to Analysis of Recursive Algorithms
- B.2 Solving Recurrences Using the Characteristic Equation
- B.3 Solving Recurrences by Substitution
- B.4 Extending Results for n, a Power of a Positive Constant b, to n in General
- B.5 Proofs of Theorems
- Exercises
- Appendix C: Data Structures for Disjoint Sets
- References
- Index
- Index_B
- Index_C
- Index_D
- Index_E
- Index_F
- Index_G
- Index_H
- Index_I
- Index_J
- Index_K
- Index_L
- Index_M
- Index_N
- Index_O
- Index_P
- Index_Q
- Index_R
- Index_S
- Index_T
- Index_U
- Index_V
- Index_W-X
- Index_Y
- Index_Z
- List of Figures
- List of Tables
- List of Algorithms, Examples, and Theorems
- List of Sidebars