# Index
### <a>C</a>
C++, [4](LiB0008.html#25), [6](LiB0008.html#29), [51](LiB0015.html#151)
*Calls(s,t)*, [430](LiB0082.html#1038)
Candidate solution, [98](LiB0026.html#268)
Ceiling, [511](LiB0093.html#1282)
Central processing unit (CPU), [486](LiB0089.html#1227)
Chachian, L.G., [401](LiB0077.html#945)
Chained Matrix Multiplication problem, [107-113](LiB0027.html#289), [377](LiB0074.html#885)
Change of variables technique, for solving recurrences, [568-571](LiB0103.html#1416)
Change problem, greedy algorithm for, [138-141](LiB0032.html#362)
Characteristic equation
definition of, [556](LiB0103.html#1388)
for homogenous linear recurrence, [556-562](LiB0103.html#1388)
solving recurrences using, [553-562](LiB0102.html#1379)
*checknode*, [191](LiB0039.html#479), [195](LiB0039.html#487), [207](LiB0042.html#516), [218](LiB0045.html#539)
Chromatic number, [384](LiB0076.html#897)
Ciphertext, [477](LiB0087.html#1202)
Clause, [391](LiB0077.html#914)
Clemen, R.T., [344](LiB0071.html#816)
Clique
definition of, [385](LiB0077.html#902)
maximal, [385](LiB0077.html#902)
Clique Decision problem, [385](LiB0077.html#902), [395-396](LiB0077.html#925)
Clique Optimization problem, [385](LiB0077.html#902)
Clique problem, [385](LiB0077.html#902)
Closed binary operation, [434](LiB0082.html#1048)
CNF-Satisfaction problem, [391-392](LiB0077.html#914)
CNF-Satisfiability, as *NP*-complete, [395-396](LiB0077.html#925)
CNF-Satisfiability Decision problem, [391-392](LiB0077.html#914)
*coalesce*, [311](LiB0065.html#740)
Codeword, [169](LiB0036.html#428)
Collision (hash clash), [341](LiB0071.html#808)
Combinations, [530](LiB0099.html#1325), [533](LiB0100.html#1333)
Common divisor, [421](LiB0081.html#999)
Common logarithms, [522](LiB0096.html#1307)
Common write protocol, [506](LiB0091.html#1271)
Commutative (abelian), [436](LiB0083.html#1057)
Complete binary tree, [285](LiB0056.html#669)
Complete quadratic functions, [25-26](LiB0010.html#75)
Completely connected network, [491](LiB0090.html#1243), [492](LiB0090.html#1245)
Complexity analysis, [17-23](LiB0009.html#56)
Complexity categories, [26-27](LiB0011.html#78), [34](LiB0011.html#106)
Complexity function, [23](LiB0010.html#70)
eventually nondecreasing, [575](LiB0105.html#1431)
nondecreasing, [573-579](LiB0105.html#1428)
smooth, [575-576](LiB0105.html#1431)
strictly increasing, [573](LiB0105.html#1428)
Composite numbers, [420-421](LiB0080.html#992)
Composite Numbers problem, [400](LiB0077.html#940)
Compressible sequences, [537](LiB0100.html#1341), [540](LiB0100.html#1348)
Computational complexity, [268-270](LiB0052.html#629)
analysis, [268-269](LiB0052.html#629)
exercises, [312-313](LiB0065.html#742)
**Compute Modular Power,** [454-456](LiB0085.html#1130)
Computer programs, for problem-solving, [2](LiB0008.html#18), [3-4](LiB0008.html#21)
Concurrent-read
concurrent-write (CRCW), [496](LiB0091.html#1254)
exclusive-write (CREW), [496-501](LiB0091.html#1254)
Conditional probability, [256-262](LiB0050.html#607)
Congruency modulo *n*, [436-442](LiB0083.html#1057)
Conjunctive normal form (CNF), [391](LiB0077.html#914)
Constant coefficients
with homogeneous linear recurrences, [553-556](LiB0102.html#1379)
with nonhomogeneous linear recurrences, [562-567](LiB0103.html#1401)
Control instructions, [24](LiB0010.html#73)
Cook, S.A., [392](LiB0077.html#917), [394](LiB0077.html#922)
Cook's Theorem, [394-395](LiB0077.html#922)
Cooper, G.F., [263-264](LiB0050.html#617)
Coopersmith, D., [71](LiB0019.html#205)
CPU (central processing unit), [486](LiB0089.html#1227)
CRCW (concurrent-read, concurrent-write), [496](LiB0091.html#1254)
CRCW PRAM algorithms, [505-508](LiB0091.html#1269)
CREW (concurrent-read, exclusive-write), [496-501](LiB0091.html#1254)
Criterion, [188](LiB0039.html#473)
Crossbar switching network, [493-494](LiB0090.html#1247)
Cryptography, [420](LiB0080.html#992)
Cycle, [97](LiB0026.html#266)
Cyclic graph, [97](LiB0026.html#266)
- 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