# List of Sidebars
## [Chapter 1:](LiB0008.html#16) Algorithms—Efficiency, Analysis, and Order
[Analysis of algorithm 1.2 Every-Case Time Complexity (Add Array Members)](LiB0010.html#61)[Analysis of algorithm 1.3 Every−Case Time Complexity (Exchange Sort)](LiB0010.html#62)[Analysis of Algorithm 1.4 Every-Case Time Complexity (Matrix Multiplication)](LiB0010.html#64)[Analysis of Algorithm 1.1 Worst−Case Time Complexity (Sequential Search)](LiB0010.html#65)[Analysis of Algorithm 1.1 Average-Case Time Complexity (Sequential Search)](LiB0010.html#67)[Analysis of Algorithm 1.1 Best-Case Time Complexity (sequential Search)](LiB0010.html#69)
## [Chapter 2:](LiB0014.html#141) Divide-and-Conquer
[Analysis of Algorithm 2.1 Worst-Case Time Complexity (Binary Search, Recursive)](LiB0015.html#152)[Analysis of Algorithm 2.3 Worse-Case Time Complexity (Merge)](LiB0016.html#164)[Analysis of Algorithm 2.2 Worst-Case Time Complexity (Mergesort)](LiB0016.html#166)[Analysis of Algorithm 2.7 Every-Case Time Complexity (Partition)](LiB0018.html#183)[Analysis of Algorithm 2.6 Worst-Case Time Complexity (Quicksort)](LiB0018.html#185)[ Analysis of Algorithm 2.6 Average-Case Time Complexity (Quicksort)](LiB0018.html#188)[Analysis of Algorithm 2.8 Every-Case Time Complexity Analysis of Number of Multiplication (Strassen)](LiB0019.html#203)[Analysis of Algorithm 2.8 Every-Case Time Complexity Analysis of Number of Additions/Subtractions (Strassen)](LiB0019.html#204)[Analysis of Algorithm 2.9 Worst-Case Time Complexity (Large Integer Multiplication)](LiB0020.html#215)[ Analysis of Algorithm 2.10 Worst-Case Time Complexity (Large Integer Multiplications 2)](LiB0020.html#219)
## [Chapter 3:](LiB0024.html#252) Dynamic Programming
[Analysis of Algorithm 3.3 Every-Case Time Complexity (Floyd's Algorithm for Shortest Paths)](LiB0026.html#279)[Analysis of Algorithm 3.6 Every-Case Time Complexity (Minimum Multiplications)](LiB0028.html#302)[Analysis of Algorithm 3.9 Every-Case Time Complexity (Optimal Binary Search Tree)](LiB0029.html#324)[Analysis of Algorithm 3.11 Every-Case Time and Space Complexity (The Dynamic Programming Algorithm for the Traveling Salesperson Problem)](LiB0030.html#343)
## [Chapter 4:](LiB0032.html#359) The Greedy Approach
[Analysis of Algorithm 4.1 Every-Case Time Complexity (Prim's Algorithm)](LiB0033.html#380)[Analysis of Algorithm 4.2 Worst-case Time-Complexity (Krukal's Algorithm)](LiB0033.html#391)[Analysis of Algorithm 4.4 Worst-Case Time Complexity (Scheduling with Deadlines)](LiB0035.html#423)
## [Chapter 7:](LiB0052.html#627) Introduction to Computational Complexity—The Sorting Problem
[Analysis of Algorithm 7.1 Worst-Case Time Complexity Analysis of Number of Comparisons of Keys (Insertion Sort)](LiB0053.html#637)[Analysis of Algorithm 7.1 Average-Case Time Complexity Analysis of Number of Comparisons of Keys (Insertion Sort)](LiB0053.html#638)[Analysis of Algorithm 7.1 Analysis of Extra Space Usage (Insertion Sort)](LiB0053.html#640)[Analysis of Algorithm 7.2 Analysis of Extra Space Usage (Mergesort 2)](LiB0055.html#655)[Analysis of Algorithm 7.4 Anallysis of Extra Space Usage (Mergesort 4)](LiB0055.html#664)[Analysis of Algorithm 7.5 Worst-Case Time Complexity (Heapsort) Analysis of Number of Comparisons of Keys (Heapsort)](LiB0059.html#687)[Analysis of Algorithm 7.5 Analysis of Extra Space Usage (Heapsort)](LiB0059.html#696)[Analysis of Algorithm 7.6 Every-Case Time Complexity (Radix Sort)](LiB0065.html#741)[Analysis of Algorithm 7.6 Analysis of Extra Space Usage (Radix Sort)](LiB0065.html#743)
## [Chapter 8:](LiB0067.html#759) More Computational Complexity—The Searching Problem
[Analysis of Algorithm 2.1 Average-Case Time Complexity (Binary Search, Recursive)](LiB0068.html#779)[Analysis of Algorithm 8.5 Average-Case Time Complexity (Selection)](LiB0072.html#851)[Analysis of Algorithm 8.6 Worst-Case Time Complexity (Selection Using the Median)](LiB0072.html#859)[Analysis of Algorithm 8.7 Expected-Value Time Complexity (Probabilistic Selection)](LiB0072.html#867)
## [Chapter 10:](LiB0080.html#989) Number-Theoretic Algorithms
[Analysis of Algorithm 10.1 Worst-Case Time Complexity (Euclid's Algorithm)](LiB0082.html#1039)[Analysis of Algorithm 10.5 Worst-Case Time Complexity (Polynomial Determine Prime)](LiB0086.html#1189)
## [Chapter 11:](LiB0089.html#1224) Introduction to Parallel Algorithms
[Analysis of Algorithm 11.3 Worst-Case Time Complexity](LiB0091.html#1268)
- 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