# Index
### <a>M</a>
Magnitude, [381](LiB0075.html#890)
*makecheap*, [292-294](LiB0059.html#686)
Marbe, K., [539](LiB0100.html#1346)
*masterlist*, [311](LiB0065.html#740)
Matching, [409](LiB0078.html#964)
Mathematical induction, [514-520](LiB0094.html#1288)
Mathematics, review of, [511-542](LiB0093.html#1282)
exercises, [542-547](LiB0100.html#1354)
functions, [513-514](LiB0093.html#1285)
lemmas, [522](LiB0096.html#1307)
logarithms, [522-526](LiB0096.html#1307)
mathematical induction, [514-520](LiB0094.html#1288)
notation, [511-513](LiB0093.html#1282)
Mathematics, review of *(continued)*
permutations, [528-529](LiB0098.html#1322)
probability, [531-542](LiB0100.html#1328)
sets, [526-528](LiB0097.html#1318)
theorems, [521-522](LiB0096.html#1303)
**Matrix Multiplication,** [8-9](LiB0008.html#33), [67](LiB0019.html#194), [268](LiB0052.html#629)
every-case time complexity, [20](LiB0010.html#63)
input size, [17](LiB0009.html#56)
McCreight, E.M., [338](LiB0070.html#803)
*m*-Coloring problem, [209](LiB0042.html#519)
Median
definition of, [361-362](LiB0072.html#853)
**Selection Using the Median,** [362-364](LiB0072.html#854)
Members, of sets, [527](LiB0098.html#1321)
Memory complexity, [23](LiB0010.html#70)
**Merge,** [55](LiB0016.html#160)
in-place sort, [57](LiB0016.html#167)
worst-case time complexity, [55-56](LiB0016.html#160)
**Merge [2](LiB0008.html#18),** [58-59](LiB0016.html#168)
**Mergesort,** [53-59](LiB0016.html#155)
average-case time complexity, [278](LiB0055.html#653)
compared with **Heapsort** and **Quicksort,** [296-297](LiB0059.html#695)
every-case time complexity, [278](LiB0055.html#653)
exercises, [313-314](LiB0066.html#746), [316](LiB0066.html#754)
improvements of, [279](LiB0055.html#654)
removal of more than one inversion after comparison, [277-278](LiB0054.html#650)
worst-case time complexity, [56-57](LiB0016.html#165), [79](LiB0021.html#224), [278](LiB0055.html#653)
**Mergesort [2](LiB0008.html#18),** [58](LiB0016.html#168)
extra space usage analysis, [279](LiB0055.html#654)
optimal threshold, [80-81](LiB0021.html#225)
**Mergesort [3](LiB0008.html#21),** [279-281](LiB0055.html#654), [503](LiB0091.html#1265)
**Mergesort [4](LiB0008.html#25) (Linked Version),** [281-283](LiB0055.html#659)
Message-passing architecture, [480](LiB0087.html#1211), [492](LiB0090.html#1245)
Miller-Rabin Randomized Primality Test, [480](LiB0087.html#1211)
MIMD (multiple instruction stream, multiple data stream), [495](LiB0091.html#1253)
*minapprox*, [409](LiB0078.html#964), [410-411](LiB0078.html#967)
*mindlist*, [409](LiB0078.html#964), [410-411](LiB0078.html#967)
*minEPL(m)*, [303-307](LiB0064.html#721)
Minimal weight matching, [409-410](LiB0078.html#964)
**Minimum Multiplications,** [113](LiB0028.html#300)
every-case time complexity, [113-114](LiB0028.html#300)
optimal order, [114-115](LiB0028.html#303)
Minimum spanning tree, [140-156](LiB0032.html#363), [407-408](LiB0078.html#958)
definition of, [143](LiB0033.html#370)
determining. *See* [**Prim's Algorithm**](LiB0125.html#1529)
optimal tour, [408](LiB0078.html#962)
Minimum Spanning Trees problem, Kruskal's algorithm, [150-155](LiB0033.html#385)
*minTND(n)*, [328-329](LiB0068.html#782)
Mises, Richard von, [536-537](LiB0100.html#1339), [539](LiB0100.html#1346), [540](LiB0100.html#1348)
Modular arithmetic review
congruency modulo *n*, [436-442](LiB0083.html#1057)
group theory, [434-436](LiB0082.html#1048)
subgroups, [442-448](LiB0083.html#1081)
Modular linear equations, solving, [448-453](LiB0083.html#1107)
Modular powers, computing, [454-456](LiB0085.html#1130)
Monet, S., [78](LiB0020.html#222)
**Monte Carlo Estimate,** [202](LiB0041.html#502)
**for Backtracking Algorithm for *n*-Queens Problem,** [203](LiB0041.html#505)
to estimate efficiency of backtracking algorithm, [200-204](LiB0040.html#499)
Monte Carlo technique, [195](LiB0039.html#487), [406](LiB0077.html#956)
Moore, E.F., [125](LiB0029.html#330)
Mosteller, F., [539](LiB0100.html#1346)
Multiple instruction stream, multiple data stream (MIMD), [489](LiB0090.html#1234)
Multiples, [420](LiB0080.html#992)
Multiplication
in computing modular powers, [440](LiB0083.html#1073)
of large integers, [72-74](LiB0020.html#208)
Munro, J.I., [78](LiB0020.html#222)
- 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