List of Algorithms, Examples, and Theorems · Foundations of Algorithms Using C++ Pseudocod

# List of Algorithms, Examples, and Theorems ## [Chapter 1:](LiB0008.html#16) Algorithms—Efficiency, Analysis, and Order [Example 1.1](LiB0008.html#20) [Example 1.2](LiB0008.html#22) [Example 1.3](LiB0008.html#23) [Example 1.4](LiB0008.html#24) [Example 1.5](LiB0008.html#26) [Algorithm 1.1:](LiB0008.html#27) Sequential Search[Algorithm 1.2:](LiB0008.html#31) Add Array Members[Algorithm 1.3:](LiB0008.html#32) Exchange Sort[Algorithm 1.4:](LiB0008.html#34) Matrix Multiplication[Algorithm 1.5:](LiB0009.html#38) Binary Search[Algorithm 1.6:](LiB0009.html#45) nth Fibonacci Term (Recursive)[Theorem 1.1](LiB0009.html#48) [Algorithm 1.7:](LiB0009.html#51) *n*th Fibonacci Term (Iterative)[Example 1.6](LiB0010.html#71) [Example 1.7](LiB0011.html#90) [Example 1.8](LiB0011.html#91) [Example 1.9](LiB0011.html#93) [Example 1.10](LiB0011.html#94) [Example 1.11](LiB0011.html#96) [Example 1.12](LiB0011.html#99) [Example 1.13](LiB0011.html#100) [Example 1.14](LiB0011.html#101) [Example 1.15](LiB0011.html#103) [Example 1.16](LiB0011.html#104) [Example 1.17](LiB0011.html#105) [Example 1.18](LiB0011.html#107) [Example 1.19](LiB0011.html#109) [Theorem 1.2](LiB0011.html#110) [Example 1.20](LiB0011.html#112) [Example 1.21](LiB0011.html#114) [Example 1.22](LiB0011.html#115) [Example 1.23](LiB0011.html#117) [Theorem 1.3](LiB0011.html#120) [Example 1.24](LiB0011.html#121) [Example 1.25](LiB0011.html#122) [Example 1.26](LiB0011.html#124) [Theorem 1.4](LiB0011.html#125) [Example 1.27](LiB0011.html#127) [Example 1.28](LiB0011.html#128) ## [Chapter 2:](LiB0014.html#141) Divide-and-Conquer [Example 2.1](LiB0015.html#146) [Algorithm 2.1:](LiB0015.html#149) Binary Search (Recursive)[Example 2.2](LiB0016.html#156) [Algorithm 2.2:](LiB0016.html#158) Mergesort[Algorithm 2.3:](LiB0016.html#161) Merge[Algorithm 2.4:](LiB0016.html#169) Mergesort 2[Algorithm 2.5:](LiB0016.html#170) Merge 2[Example 2.3](LiB0018.html#175) [Algorithm 2.6:](LiB0018.html#177) Quicksort[Algorithm 2.7:](LiB0018.html#179) Partition[Example 2.4](LiB0019.html#195) [Example 2.5](LiB0019.html#198) [Algorithm 2.8:](LiB0019.html#201) Strassen[Example 2.6](LiB0020.html#212) [Algorithm 2.9:](LiB0020.html#214) Large Integer Multiplication[Algorithm 2.10:](LiB0020.html#218) Large Integer Multiplication 2[Example 2.7](LiB0021.html#226) [Example 2.8](LiB0021.html#231) ## [Chapter 3:](LiB0024.html#252) Dynamic Programming [Algorithm 3.1:](LiB0025.html#258) Binomial Coefficient Using Divide-and-Conquer[Example 3.1](LiB0025.html#261) [Algorithm 3.2:](LiB0025.html#263) Binomial Coefficient Using Dynamic Programming[Example 3.2](LiB0026.html#271) [Example 3.3](LiB0026.html#275) [Algorithm 3.3:](LiB0026.html#277) Floyd's Algorithm for Shortest Paths[Algorithm 3.4:](LiB0026.html#280) Floyd's Algorithm for Shortest Paths 2[Algorithm 3.5:](LiB0026.html#283) Print Shortest Path[Example 3.4](LiB0027.html#287) [Example 3.5](LiB0028.html#294) [Example 3.6](LiB0028.html#298) [Algorithm 3.6:](LiB0028.html#301) Minimum Multiplications[Algorithm 3.7:](LiB0028.html#306) Print Optimal Order[Algorithm 3.8:](LiB0029.html#312) Search Binary Tree[Example 3.7](LiB0029.html#314) [Example 3.8](LiB0029.html#317) [Algorithm 3.9:](LiB0029.html#322) Optimal Binary Search Tree[Algorithm 3.10:](LiB0029.html#325) Build Optimal Binary Search Tree[Example 3.9](LiB0029.html#327) [Example 3.10](LiB0030.html#336) [Example 3.11](LiB0030.html#338) [Algorithm 3.11:](LiB0030.html#340) The Dynamic Programming Algorithm for the Traveling Salesperson Problem[Theorem 3.1](LiB0030.html#342) [Example 3.12](LiB0030.html#345) ## [Chapter 4:](LiB0032.html#359) The Greedy Approach [Example 4.1](LiB0033.html#371) [Algorithm 4.1:](LiB0033.html#378) Prim's Algorithm[Lemma 4.1](LiB0033.html#381) [Theorem 4.1](LiB0033.html#384) [Algorithm 4.2:](LiB0033.html#389) Kruskal's Algorithm[Lemma 4.2](LiB0033.html#393) [Theorem 4.2](LiB0033.html#395) [Algorithm 4.3:](LiB0034.html#403) Dijkstra's Algorithm[Example 4.2](LiB0035.html#408) [Theorem 4.3](LiB0035.html#410) [Example 4.3](LiB0035.html#413) [Example 4.4](LiB0035.html#416) [Lemma 4.3](LiB0035.html#418) [Example 4.5](LiB0035.html#419) [Algorithm 4.4:](LiB0035.html#420) Scheduling with Deadlines[Example 4.6](LiB0035.html#422) [Theorem 4.4](LiB0035.html#425) [Example 4.7](LiB0036.html#432) [Example 4.8](LiB0036.html#438) [Lemma 4.4](LiB0036.html#441) [Theorem 4.5](LiB0036.html#443) [Example 4.9](LiB0037.html#456) ## [Chapter 5:](LiB0039.html#471) Backtracking [Example 5.1](LiB0039.html#482) [Algorithm 5.1:](LiB0040.html#492) The Backtracking Algorithm for the *n*-Queens Problem[Algorithm 5.2:](LiB0041.html#503) Monte Carlo Estimate[Algorithm 5.3:](LiB0041.html#504) Monte Carlo Estimate for Algorithm 5.1 (The Backtracking Algorithm for the *n*-Queens Problem)[Example 5.2](LiB0042.html#508) [Example 5.3](LiB0042.html#511) [Example 5.4](LiB0042.html#514) [Algorithm 5.4:](LiB0042.html#517) The Backtracking Algorithm for the Sum-of-Subsets Problem[Example 5.5](LiB0043.html#521) [Algorithm 5.5:](LiB0043.html#527) The Backtracking Algorithm for the, m-Coloring Problem[Algorithm 5.6:](LiB0044.html#534) The Backtracking Algorithm for the Hamiltonian Circuits Problem[Example 5.6](LiB0045.html#541) [Algorithm 5.7:](LiB0045.html#548) The Backtracking Algorithm for the 0–1 Knapsack Problem ## [Chapter 6:](LiB0047.html#565) Branch-and-Bound [Example 6.1](LiB0048.html#573) [Algorithm 6.1](LiB0048.html#579)[Example 6.2](LiB0048.html#583) [Algorithm 6.2](LiB0048.html#589)[Example 6.3](LiB0049.html#598) [Algorithm 6.3](LiB0049.html#603)[Theorem 6.1](LiB0050.html#608)[Example 6.4](LiB0050.html#610) [Algorithm 6.4](LiB0050.html#618) ## [Chapter 7:](LiB0052.html#627) Introduction to Computational Complexity—The Sorting Problem [Algorithm 7.1:](LiB0053.html#634) Insertion Sort[Algorithm 7.2:](LiB0053.html#644) Selection Sort[Theorem 7.1](LiB0054.html#649) [Algorithm 7.3:](LiB0055.html#657) Mergesort 3 (Dynamic Programming Version)[Algorithm 7.4:](LiB0055.html#661) Mergesort 4 (Linked Version)[Analysis of Extra Space Usage (Improved Quicksort)](LiB0056.html#668)[Algorithm 7.5:](LiB0059.html#685) Heapsort[Lemma 7.1](LiB0062.html#709) [Lemma 7.2](LiB0063.html#712) [Lemma 7.3](LiB0063.html#713) [Theorem 7.2](LiB0063.html#716) [Lemma 7.4](LiB0063.html#718) [Theorem 7.3](LiB0063.html#719) [Lemma 7.5](LiB0064.html#722) [Lemma 7.6](LiB0064.html#723) [Lemma 7.7](LiB0064.html#725) [Lemma 7.8](LiB0064.html#727) [Lemma 7.9](LiB0064.html#729) [Lemma 7.10](LiB0064.html#730) [Theorem 7.4](LiB0064.html#732) [Algorithm 7.6:](LiB0065.html#739) Radix Sort ## [Chapter 8:](LiB0067.html#759) More Computational Complexity—The Searching Problem [Lemma 8.1](LiB0068.html#769) [Lemma 8.2](LiB0068.html#771) [Theorem 8.1](LiB0068.html#773) [Lemma 8.3](LiB0068.html#776) [Lemma 8.4](LiB0068.html#783) [Lemma 8.5](LiB0068.html#785) [Lemma 8.6](LiB0068.html#786) [Theorem 8.2](LiB0068.html#787) [Alogrithm 8.1:](LiB0069.html#791) Interpolation Search[Theorem 8.3](LiB0070.html#801) [Theorem 8.4](LiB0071.html#811) [Theorem 8.5](LiB0071.html#812) [Example 8.1](LiB0071.html#813) [Theorem 8.6](LiB0071.html#815) [Alogrithm 8.2:](LiB0072.html#822) Find Largest Key[Theorem 8.7](LiB0072.html#823) [Alogrithm 8.3:](LiB0072.html#826) Find Smallest and Largest Keys[Alogrithm 8.4:](LiB0072.html#828) Find Smallest and Largest Keys by Pairing Keys[Example 8.2](LiB0072.html#835) [Theorem 8.8](LiB0072.html#838) [Theorem 8.9](LiB0072.html#844) [Alogrithm 8.5:](LiB0072.html#849) Selection[Alogrithm 8.6:](LiB0072.html#856) Selection Using the Median[Alogrithm 8.7:](LiB0072.html#864) Probabilistic Selection ## [Chapter 9:](LiB0074.html#880) Computational Complexity and Interactability—An Introduction to the Theory of NP [Example 9.1](LiB0074.html#884) [Example 9.2:](LiB0077.html#899) Traveling Salesperson Problem[Example 9.3:](LiB0077.html#900) 0–1 Knapsack Problem[Example 9.4:](LiB0077.html#901) Graph–Coloring Problem[Example 9.5:](LiB0077.html#903) Clique Problem[Example 9.6:](LiB0077.html#915) CNF–Satisfiability Problem[Example 9.7](LiB0077.html#916) [Example 9.8:](LiB0077.html#919) A Transformation Algorithm[Theorem 9.1](LiB0077.html#921)[Theorem 9.2](LiB0077.html#923)[Theorem 9.3](LiB0077.html#924)[Example 9.9](LiB0077.html#926) [Example 9.10](LiB0077.html#930) [Example 9.11](LiB0077.html#932) [Example 9.12:](LiB0077.html#937) Graph Isomorphism Problem[Theorem 9.4](LiB0077.html#939)[Example 9.13:](LiB0077.html#942) Primes Problem[Example 9.14:](LiB0077.html#943) Composite Numbers Problem[Example 9.15:](LiB0077.html#944) Complementary Traveling Salesperson Decision Problem[Theorem 9.5](LiB0077.html#946)[Example 9.16:](LiB0077.html#949) The Traveling Salesperson Optimization Problem Is *NP*–hard[Example 9.17](LiB0077.html#953) [Example 9.18:](LiB0078.html#960) Traveling Salesperson Problem with Triangular Inequality[Theorem 9.6](LiB0078.html#965)[Theorem 9.7](LiB0078.html#968)[Example 9.19](LiB0078.html#971) [Lemma 9.1](LiB0078.html#974)[Lemma 9.2](LiB0078.html#978)[Theorem 9.8](LiB0078.html#980) ## [Chapter 10:](LiB0080.html#989) Number-Theoretic Algorithms [Example 10.1](LiB0081.html#995) [Example 10.2](LiB0081.html#996) [Example 10.3](LiB0081.html#997) [Example 10.4](LiB0081.html#998) [Example 10.5](LiB0081.html#1001) [Theorem 10.1](LiB0081.html#1002)[Example 10.6](LiB0081.html#1004) [Theorem 10.2](LiB0081.html#1005)[Example 10.7](LiB0081.html#1007) [Corollary 10.1](LiB0081.html#1008)[Example 10.8](LiB0081.html#1009) [Theorem 10.3](LiB0081.html#1010)[Example 10.9](LiB0081.html#1012) [Example 10.10](LiB0081.html#1014) [Theorem 10.4](LiB0081.html#1015)[Example 10.11](LiB0081.html#1017) [Corollary 10.2](LiB0081.html#1018)[Theorem 10.5](LiB0081.html#1019)[Example 10.12](LiB0081.html#1021) [Theorem 10.6](LiB0081.html#1022)[Example 10.13](LiB0081.html#1023) [Example 10.14](LiB0081.html#1026) [Theorem 10.7](LiB0081.html#1027)[Example 10.15](LiB0081.html#1028) [Example 10.16](LiB0082.html#1030) [Algorithm 10.1 **Euclid's Algorithm**](LiB0082.html#1033)[Example 10.17](LiB0082.html#1034) [Lemma 10.1](LiB0082.html#1035)[Theorem 10.8](LiB0082.html#1037)[Algorithm 10.2 Euclid's Algorithm 2](LiB0082.html#1043)[Example 10.18](LiB0082.html#1044) [Theorem 10.9](LiB0082.html#1047)[Example 10.19](LiB0083.html#1051) [Example 10.20](LiB0083.html#1052) [Example 10.21](LiB0083.html#1053) [Theorem 10.10](LiB0083.html#1055)[Theorem 10.11](LiB0083.html#1056)[Example 10.22](LiB0083.html#1059) [Theorem 10.12](LiB0083.html#1060)[Example 10.23](LiB0083.html#1061) [Theorem 10.13](LiB0083.html#1062)[Example 10.24](LiB0083.html#1064) [Theorem 10.14](LiB0083.html#1066)[Example 10.25](LiB0083.html#1067) [Example 10.26](LiB0083.html#1068) [Example 10.27](LiB0083.html#1070) [Theorem 10.15](LiB0083.html#1071)[Example 10.28](LiB0083.html#1072) [Example 10.29](LiB0083.html#1074) [Example 10.30](LiB0083.html#1075) [Example 10.31](LiB0083.html#1076) [Theorem 10.16](LiB0083.html#1078)[Example 10.32](LiB0083.html#1079) [Theorem 10.17](LiB0083.html#1080)[Example 10.33](LiB0083.html#1082) [Example 10.34](LiB0083.html#1083) [Example 10.35](LiB0083.html#1084) [Example 10.36](LiB0083.html#1086) [Theorem 10.18](LiB0083.html#1087)[Theorem 10.19](LiB0083.html#1089)[Example 10.37](LiB0083.html#1090) [Corollary 10.3](LiB0083.html#1091)[Example 10.38](LiB0083.html#1093) [Theorem 10.20](LiB0083.html#1094)[Example 10.39](LiB0083.html#1096) [Example 10.40](LiB0083.html#1097) [Example 10.41](LiB0083.html#1098) [Corollary 10.4](LiB0083.html#1100)[Example 10.42](LiB0083.html#1101) [Corollary 10.5](LiB0083.html#1102)[Theorem 10.21](LiB0083.html#1104)[Example 10.43](LiB0083.html#1105) [Theorem 10.22](LiB0083.html#1106)[Example 10.44](LiB0083.html#1108) [Example 10.45](LiB0084.html#1111) [Theorem 10.23](LiB0084.html#1112)[Corollary 10.6](LiB0084.html#1114)[Corollary 10.7](LiB0084.html#1116)[Corollary 10.8](LiB0084.html#1117)[Example 10.46](LiB0084.html#1118) [Example 10.47](LiB0084.html#1119) [Example 10.48](LiB0084.html#1121) [Theorem 10.24](LiB0084.html#1122)[Example 10.49](LiB0084.html#1123) [Theorem 10.25](LiB0084.html#1125)[Example 10.50](LiB0084.html#1126) [Algorithm 10.3 Solve Modular Linear Equation](LiB0084.html#1128)[Example 10.51](LiB0085.html#1131) [Algorithm 10.4 Compute Modular Power](LiB0085.html#1132)[Example 10.52](LiB0085.html#1134) [Theorem 10.26](LiB0085.html#1136)[Theorem 10.27](LiB0086.html#1141)[Example 10.53](LiB0086.html#1142) [Example 10.54](LiB0086.html#1143) [Example 10.55](LiB0086.html#1147) [Example 10.56](LiB0086.html#1149) [Example 10.57](LiB0086.html#1150) [Example 10.58](LiB0086.html#1151) [Lemma 10.2](LiB0086.html#1153)[Theorem 10.28](LiB0086.html#1154)[Example 10.59](LiB0086.html#1156) [Example 10.60](LiB0086.html#1157) [Example 10.61](LiB0086.html#1159) [Example 10.62](LiB0086.html#1160) [Example 10.63](LiB0086.html#1161) [Example 10.64](LiB0086.html#1163) [Theorem 10.29](LiB0086.html#1164)[Example 10.65](LiB0086.html#1165) [Algorithm 10.5 Polynomial Determine Prime](LiB0086.html#1167)[Theorem 10.30](LiB0086.html#1170)[Lemma 10.3](LiB0086.html#1171)[Lemma 10.4](LiB0086.html#1173)[Lemma 10.5](LiB0086.html#1175)[Lemma 10.6](LiB0086.html#1176)[LEMMA 10.7](LiB0086.html#1178)[Theorem 10.31](LiB0086.html#1179)[Lemma 10.8](LiB0086.html#1183)[Lemma 10.9](LiB0086.html#1184)[Lemma 10.10](LiB0086.html#1185)[Theorem 10.32](LiB0086.html#1186)[Lemma 10.11](LiB0086.html#1193)[Lemma 10.12](LiB0086.html#1194)[Lemma 10.13](LiB0086.html#1196)[Lemma 10.14](LiB0086.html#1197)[Lemma 10.15](LiB0086.html#1198)[Example 10.66](LiB0087.html#1203) [Theorem 10.33](LiB0087.html#1208) ## [Chapter 11:](LiB0089.html#1224) Introduction to Parallel Algorithms [Algorithm 11.1:](LiB0091.html#1261) Parallel Find Largest Key[Algorithm 11.2:](LiB0091.html#1263) Parallel Binomial Coefficient[Algorithm 11.3:](LiB0091.html#1266) Parallel Mergesort[Algorithm 11.4:](LiB0091.html#1273) Parallel CRCW Find Largest Key ## [Appendix A:](LiB0093.html#1281) Review of Necessary Mathematics [Example A.1](LiB0095.html#1293) [Example A.2](LiB0095.html#1295) [Example A.3](LiB0095.html#1297) [Example A.4](LiB0095.html#1299) [Example A.5](LiB0095.html#1301) [Theorem A.1](LiB0096.html#1304) [Theorem A.2](LiB0096.html#1305) [Theorem A.3](LiB0096.html#1306) [Example A.6](LiB0097.html#1310) [Example A.7](LiB0097.html#1312) [Example A.8](LiB0097.html#1313) [Example A.9](LiB0097.html#1319) [Example A.10](LiB0099.html#1326) [Example A.11](LiB0100.html#1329) [Example A.12](LiB0100.html#1331) [Example A.13](LiB0100.html#1332) [Example A.14](LiB0100.html#1334) [Example A.15](LiB0100.html#1338) [Example A.16](LiB0100.html#1343) [Example A.17](LiB0100.html#1344) [Example A.18](LiB0100.html#1345) [Example A.19](LiB0100.html#1347) [Example A.20](LiB0100.html#1350) [Example A.21](LiB0100.html#1352) [Example A.22](LiB0100.html#1353) ## [Appendix B:](LiB0102.html#1369) Solving Recurrence Equations—With Applications to Analysis of Recursive Algorithms [Algorithm B.1:](LiB0102.html#1372) Factorial[Example B.1](LiB0102.html#1375) [Example B.2](LiB0102.html#1377) [Example B.3](LiB0102.html#1378) [Example B.4](LiB0103.html#1382) [Example B.5](LiB0103.html#1384) [Example B.6](LiB0103.html#1385) [Example B.7](LiB0103.html#1390) [Theorem B.1](LiB0103.html#1391) [Example B.8](LiB0103.html#1392) [Example B.9](LiB0103.html#1394) [Theorem B.2](LiB0103.html#1397) [Example B.10](LiB0103.html#1398) [Example B.11](LiB0103.html#1400) [Example B.12](LiB0103.html#1403) [Example B.13](LiB0103.html#1404) [Example B.14](LiB0103.html#1406) [Theorem B.3](LiB0103.html#1408) [Example B.15](LiB0103.html#1410) [Example B.16](LiB0103.html#1412) [Example B.17](LiB0103.html#1414) [Example B.18](LiB0103.html#1417) [Example B.19](LiB0103.html#1419) [Example B.20](LiB0103.html#1421) [Example B.21](LiB0104.html#1424) [Example B.22](LiB0104.html#1426) [Example B.23](LiB0105.html#1432) [Example B.24](LiB0105.html#1433) [Theorem B.4](LiB0105.html#1434) [Example B.25](LiB0105.html#1436) [Theorem B.5](LiB0105.html#1438) [Example B.26](LiB0105.html#1440) [Example B.27](LiB0105.html#1441) [Theorem B.6](LiB0105.html#1443) [Example B.28](LiB0105.html#1444) [Lemma B.1](LiB0106.html#1446) ## [Appendix C:](LiB0108.html#1464) Data Structures for Disjoint Sets [Disjoint Set Data Structure](LiB0108.html#1471)[Disjoint Set Data Structure II](LiB0108.html#1478)[Disjoint Set Data Structure III](LiB0108.html#1481)