|
Algorithms: Efficiency, Analysis, and Order |
|
|
1 | (46) |
|
|
2 | (7) |
|
The Importance of Developing Efficient Algorithms |
|
|
9 | (8) |
|
Sequential Search Versus Binary Search |
|
|
9 | (3) |
|
|
12 | (5) |
|
|
17 | (8) |
|
|
17 | (7) |
|
|
24 | (1) |
|
|
24 | (1) |
|
|
25 | (16) |
|
An Intuitive Introduction to Order |
|
|
25 | (2) |
|
A Rigorous Introduction to Order |
|
|
27 | (12) |
|
Using a Limit to Determine Order |
|
|
39 | (2) |
|
|
41 | (6) |
|
|
42 | (5) |
|
|
47 | (44) |
|
|
48 | (5) |
|
|
53 | (6) |
|
The Divide-and-Conquer Approach |
|
|
59 | (1) |
|
Quicksort (Partition Exchange Sort) |
|
|
60 | (7) |
|
Strassen's Matrix Multiplication Algorithm |
|
|
67 | (5) |
|
Arithmetic with Large Numbers |
|
|
72 | (6) |
|
Representation of Large Integers: Addition and Other Linear-Time Operations |
|
|
72 | (1) |
|
Multiplication of Large Integers |
|
|
72 | (6) |
|
|
78 | (4) |
|
When Not to Use Divide-and-Conquer |
|
|
82 | (9) |
|
|
83 | (8) |
|
|
91 | (46) |
|
|
92 | (5) |
|
Floyd's Algorithm for Shortest Paths |
|
|
97 | (8) |
|
Dynamic Programming and Optimization Problems |
|
|
105 | (2) |
|
Chained Matrix Multiplication |
|
|
107 | (9) |
|
Optimal Binary Search Trees |
|
|
116 | (9) |
|
The Traveling Salesperson Problem |
|
|
125 | (12) |
|
|
133 | (4) |
|
|
137 | (50) |
|
|
140 | (16) |
|
|
144 | (6) |
|
|
150 | (5) |
|
Comparing Prim's Algorithm with Kruskal's Algorithm |
|
|
155 | (1) |
|
|
155 | (1) |
|
Dijkstra's Algorithm for Single-Source Shortest Paths |
|
|
156 | (3) |
|
|
159 | (10) |
|
Minimizing Total Time in the System |
|
|
160 | (2) |
|
Scheduling with Deadlines |
|
|
162 | (7) |
|
|
169 | (6) |
|
|
170 | (1) |
|
|
171 | (4) |
|
The Greedy Approach Versus Dynamic Programming: The Knapsack Problem |
|
|
175 | (12) |
|
A Greedy Approach to the 0-1 Knapsack Problem |
|
|
175 | (2) |
|
A Greedy Approach to the Fractional Knapsack Problem |
|
|
177 | (1) |
|
A Dynamic Programming Approach to the 0-1 Knapsack Problem |
|
|
177 | (1) |
|
A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem |
|
|
178 | (3) |
|
|
181 | (6) |
|
|
187 | (46) |
|
The Backtracking Technique |
|
|
188 | (8) |
|
|
196 | (4) |
|
Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm |
|
|
200 | (4) |
|
The Sum-of-Subsets Problem |
|
|
204 | (5) |
|
|
209 | (5) |
|
The Hamiltonian Circuits Problem |
|
|
214 | (3) |
|
|
217 | (16) |
|
A Backtracking Algorithm for the 0-1 Knapsack Problem |
|
|
217 | (10) |
|
Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem |
|
|
227 | (1) |
|
|
227 | (6) |
|
|
233 | (34) |
|
Illustrating Branch-and-Bound with the 0-1 Knapsack Problem |
|
|
235 | (11) |
|
Breadth-First Search with Branch-and-Bound Pruning |
|
|
235 | (6) |
|
Best-First Search with Branch-and-Bound Pruning |
|
|
241 | (5) |
|
The Traveling Salesperson Problem |
|
|
246 | (9) |
|
Abductive Inference (Diagnosis) |
|
|
255 | (12) |
|
|
264 | (3) |
|
Introduction to Computational Complexity: The Sorting Problem |
|
|
267 | (52) |
|
|
268 | (2) |
|
Insertion Sort and Selection Sort |
|
|
270 | (5) |
|
Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison |
|
|
275 | (2) |
|
|
277 | (6) |
|
|
283 | (2) |
|
|
285 | (11) |
|
Heaps and Basic Heap Routines |
|
|
285 | (4) |
|
An Implementation of Heapsort |
|
|
289 | (7) |
|
Comparison of Mergesort, Quicksort, and Heapsort |
|
|
296 | (1) |
|
Lower Bounds for Sorting Only by Comparison of Keys |
|
|
297 | (11) |
|
Decision Trees for Sorting Algorithms |
|
|
297 | (3) |
|
Lower Bounds for Worst-Case Behavior |
|
|
300 | (3) |
|
Lower Bounds for Average-Case Behavior |
|
|
303 | (5) |
|
Sorting by Distribution (Radix Sort) |
|
|
308 | (11) |
|
|
312 | (7) |
|
More Computational Complexity: The Searching Problem |
|
|
319 | (56) |
|
Lower Bounds for Searching Only by Comparisons of Keys |
|
|
320 | (10) |
|
Lower Bounds for Worst-Case Behavior |
|
|
322 | (2) |
|
Lower Bounds for Average-Case Behavior |
|
|
324 | (6) |
|
|
330 | (3) |
|
|
333 | (6) |
|
|
334 | (4) |
|
|
338 | (1) |
|
|
339 | (5) |
|
The Selection Problem: Introduction to Adversary Arguments |
|
|
344 | (31) |
|
|
345 | (1) |
|
Finding Both the Smallest and Largest Keys |
|
|
346 | (7) |
|
Finding the Second-Largest Key |
|
|
353 | (5) |
|
Finding the kth-Smallest Key |
|
|
358 | (8) |
|
A Probabilistic Algorithm for the Selection Problem |
|
|
366 | (4) |
|
|
370 | (5) |
|
Computational Complexity and Intractability: An Introduction to the Theory of NP |
|
|
375 | (44) |
|
|
376 | (2) |
|
|
378 | (4) |
|
The Three General Problems |
|
|
382 | (2) |
|
Problems for Which Polynomial-Time Algorithms Have Been Found |
|
|
382 | (1) |
|
Problems That Have Been Proven to Be Intractable |
|
|
382 | (1) |
|
Problems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found |
|
|
383 | (1) |
|
|
384 | (22) |
|
|
386 | (4) |
|
|
390 | (12) |
|
NP-Hard, NP-Easy, and NP-Equivalent Problems |
|
|
402 | (4) |
|
Handling NP-Hard Problems |
|
|
406 | (13) |
|
An Approximation Algorithm for the Traveling Salesperson Problem |
|
|
407 | (4) |
|
An Approximation Algorithm for the Bin-Packing Problem |
|
|
411 | (5) |
|
|
416 | (3) |
|
Number-Theoretic Algorithms |
|
|
419 | (66) |
|
|
420 | (7) |
|
Composite and Prime Numbers |
|
|
420 | (1) |
|
|
421 | (3) |
|
|
424 | (3) |
|
|
427 | (1) |
|
Computing the Greatest Common Divisor |
|
|
427 | (7) |
|
|
428 | (4) |
|
An Extension to Euclid's Algorithm |
|
|
432 | (2) |
|
Modular Arithmetic Review |
|
|
434 | (14) |
|
|
434 | (2) |
|
|
436 | (6) |
|
|
442 | (6) |
|
Solving Modular Linear Equations |
|
|
448 | (6) |
|
|
454 | (2) |
|
Finding Large Prime Numbers |
|
|
456 | (20) |
|
Searching for a Large Prime |
|
|
457 | (1) |
|
Checking if a Number Is Prime |
|
|
458 | (18) |
|
The RSA Public-Key Cryptosystem |
|
|
476 | (9) |
|
|
476 | (1) |
|
|
477 | (3) |
|
|
480 | (5) |
|
Introduction to Parallel Algorithms |
|
|
485 | (26) |
|
|
488 | (7) |
|
|
488 | (2) |
|
Address-Space Organization |
|
|
490 | (1) |
|
|
491 | (4) |
|
|
495 | (16) |
|
Designing Algorithms for the CREW PRAM Model |
|
|
497 | (8) |
|
Designing Algorithms for the CRCW PRAM Model |
|
|
505 | (3) |
|
|
508 | (3) |
|
Appendix A Review of Necessary Mathematics |
|
|
511 | (38) |
|
|
511 | (2) |
|
|
513 | (1) |
|
A.3 Mathematical Induction |
|
|
514 | (7) |
|
|
521 | (1) |
|
|
522 | (4) |
|
A.5.1 Definition and Properties of Logarithms |
|
|
522 | (2) |
|
A.5.2 The Natural Logarithm |
|
|
524 | (2) |
|
|
526 | (2) |
|
A.7 Permutations and Combinations |
|
|
528 | (3) |
|
|
531 | (18) |
|
|
536 | (4) |
|
|
540 | (2) |
|
|
542 | (7) |
|
Appendix B Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms |
|
|
549 | (40) |
|
B.1 Solving Recurrences Using Induction |
|
|
549 | (4) |
|
B.2 Solving Recurrences Using the Characteristic Equation |
|
|
553 | (18) |
|
B.2.1 Homogeneous Linear Recurrences |
|
|
553 | (9) |
|
B.2.2 Nonhomogeneous Linear Recurrences |
|
|
562 | (6) |
|
B.2.3 Change of Variables (Domain Transformations) |
|
|
568 | (3) |
|
B.3 Solving Recurrences by Substitution |
|
|
571 | (2) |
|
B.4 Extending Results for n, a Power of a Positive Constant b, to n in General |
|
|
573 | (6) |
|
|
579 | (10) |
|
|
582 | (7) |
|
Appendix C Data Structures for Disjoint Sets |
|
|
589 | (10) |
References |
|
599 | (6) |
Index |
|
605 | |