# Index
### <a>B</a>
B(*n*) (best-case time complexity), [22-23](LiB0010.html#68)
Backtracking, [187-188](LiB0038.html#469)
definition of, [191](LiB0039.html#479)
exercises, [227-231](LiB0045.html#552)
*n*-Queens problem, [196-200](LiB0040.html#489)
technique, [188-195](LiB0039.html#473)
**Backtracking**
efficiency, estimating, [200-204](LiB0040.html#499)
**for the Hamiltonian Circuits Problem,** [215-216](LiB0044.html#533)
for 0-1 Knapsack problem, [217-227](LiB0044.html#536)
**for the *m*-Coloring Problem,** [211-213](LiB0043.html#525)
**for *n*-Queens Problem,** [197-200](LiB0040.html#491), [202-203](LiB0041.html#502)
**for Sum-of-Subsets Problem,** [208](LiB0042.html#518)
Baker, R.C., [470](LiB0086.html#1182)
Base, [523](LiB0097.html#1311)
Basic operation, [18](LiB0010.html#59). *See also* under specific algorithms
Bayer, R., [338](LiB0070.html#803)
Bayesian network, [262](LiB0050.html#615)
definition of, [256](LiB0050.html#607)
elements of, [406](LiB0077.html#956)
for parallel computers, [486-488](LiB0089.html#1227)
Bentley, J.L., [579](LiB0105.html#1442)
Best-case time complexity (B(*n*)), [22-23](LiB0010.html#68)
**Best-First Search with Branch-and-Bound Pruning,** [234](LiB0047.html#568), [241-246](LiB0048.html#581)
**for Abductive Inference,** [263-264](LiB0050.html#617)
**for 0-1 Knapsack problem,** [245-246](LiB0048.html#588)
pruned state space tree, [256-262](LiB0050.html#607)
Big *O*, [27-31](LiB0011.html#80)
Binary code, [169](LiB0036.html#428)
**Binary Search,** [9-11](LiB0008.html#35)
average-case performance, [330](LiB0068.html#788)
basic operation, [18](LiB0010.html#59)
hashing and, [343](LiB0071.html#814)
input size, [17](LiB0009.html#56)
lower bounds, [321](LiB0068.html#764), [324-325](LiB0068.html#772)
searching in trees, [333-334](LiB0069.html#793). *See also* [Binary search trees](#binarysearchtrees)
time complexity, [320](LiB0067.html#762)
*vs.* **Sequential Search,** [9-11](LiB0008.html#35)
**Binary Search Recursive,** [48-51](LiB0014.html#144)
average-case time complexity analysis, [325-330](LiB0068.html#777)
worst-case time complexity, [52](LiB0015.html#153)
Binary search trees, [334-338](LiB0070.html#795)
balanced, [116-117](LiB0028.html#307)
definition of, [116](LiB0028.html#307)
depth of node, [116](LiB0028.html#307), [118](LiB0029.html#311)
depth of tree, [116](LiB0028.html#307)
level of node, [116](LiB0028.html#307)
nearly complete, [324](LiB0068.html#772)
optimal, [117](LiB0029.html#310), [120](LiB0029.html#316)
search key, [117](LiB0029.html#310)
with three keys, [119-122](LiB0029.html#313)
**Binomial Coefficient,** [92-93](LiB0024.html#255), [530](LiB0099.html#1325)
**using divide-and-conquer,** [93-95](LiB0025.html#257)
**using dynamic programming,** [95-96](LiB0025.html#262)
Binomial theorem, [530](LiB0099.html#1325)
Bin-Packing problem, approximation algorithm,411-416
Blum, M., [366](LiB0072.html#861)
Bool, [6](LiB0008.html#29)
Borodin, A.B., [78](LiB0020.html#222)
Bottom node, [285-286](LiB0056.html#669)
Bottom-up approach, [92](LiB0024.html#255)
Bound, [218-225](LiB0045.html#539)
Bounded-degree network, [492](LiB0090.html#1245), [493](LiB0090.html#1247)
Branch, [174](LiB0036.html#442)
Branch-and-bound pruning, [233-264](LiB0047.html#567)
exercises, [264-266](LiB0050.html#619)
0-1 Knapsack problem, [235-246](LiB0047.html#569)
Traveling Salesperson problem, [246-255](LiB0048.html#590)
Brassard, G., [39](LiB0011.html#118), [71](LiB0019.html#205), [78](LiB0020.html#222)
Bratley, P., [71](LiB0019.html#205)
**Breadth-First Search with Branch-and-Bound Pruning,** [234-235](LiB0047.html#568)
*dequeue*, [235](LiB0047.html#569)
**for 0-1 Knapsack problem,** [239-241](LiB0048.html#578)
B-trees, [338-339](LiB0070.html#803)
**Build Optimal Binary Search Tree,** [123-125](LiB0029.html#323)
- 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