| |
| |
| |
Algorithms: Efficiency, Analysis, and Order | |
| |
| |
| |
Algorithms | |
| |
| |
| |
The Importance of Developing Efficient Algorithms | |
| |
| |
| |
Sequential Search Versus Binary Search | |
| |
| |
| |
The Fibonacci Sequence | |
| |
| |
| |
Analysis of Algorithms | |
| |
| |
| |
Complexity Analysis | |
| |
| |
| |
Applying the Theory | |
| |
| |
| |
Analysis of Correctness | |
| |
| |
| |
Order | |
| |
| |
| |
An Intuitive Introduction to Order | |
| |
| |
| |
A Rigorous Introduction to Order | |
| |
| |
| |
Using a Limit to Determine Order | |
| |
| |
| |
Outline of This Book | |
| |
| |
Exercises | |
| |
| |
| |
Divide-and-Conquer | |
| |
| |
| |
Binary Search | |
| |
| |
| |
Mergesort | |
| |
| |
| |
The Divide-and-Conquer Approach | |
| |
| |
| |
Quicksort (Partition Exchange Sort) | |
| |
| |
| |
Strassen's Matrix Multiplication Algorithm | |
| |
| |
| |
Arithmetic with Large Numbers | |
| |
| |
| |
Representation of Large Integers: Addition and Other Linear-Time Operations | |
| |
| |
| |
Multiplication of Large Integers | |
| |
| |
| |
Determining Thresholds | |
| |
| |
| |
When Not to Use Divide-and-Conquer | |
| |
| |
Exercises | |
| |
| |
| |
Dynamic Programming | |
| |
| |
| |
The Binomial Coefficient | |
| |
| |
| |
Floyd's Algorithm for Shortest Paths | |
| |
| |
| |
Dynamic Programming and Optimization Problems | |
| |
| |
| |
Chained Matrix Multiplication | |
| |
| |
| |
Optimal Binary Search Trees | |
| |
| |
| |
The Traveling Salesperson Problem | |
| |
| |
| |
Sequence Alignment | |
| |
| |
Exercises | |
| |
| |
| |
The Greedy Approach | |
| |
| |
| |
Minimum Spanning Trees | |
| |
| |
| |
Prim's Algorithm | |
| |
| |
| |
Kruskal's Algorithm | |
| |
| |
| |
Comparing Prim's Algorithm with Kruskal's Algorithm | |
| |
| |
| |
Final Discussion | |
| |
| |
| |
Dijkstra's Algorithm for Single-Source Shortest Paths | |
| |
| |
| |
Scheduling | |
| |
| |
| |
Minimizing Total Time in the System | |
| |
| |
| |
Scheduling with Deadlines | |
| |
| |
| |
Huffman Code | |
| |
| |
| |
Prefix Codes | |
| |
| |
| |
Huffman's Algorithm | |
| |
| |
| |
The Greedy Approach Versus Dynamic Programming: The Knapsack Problem | |
| |
| |
| |
A Greedy Approach to the 0-1 Knapsack Problem | |
| |
| |
| |
A Greedy Approach to the Fractional Knapsack Problem | |
| |
| |
| |
A Dynamic Programming Approach to the 0-1 Knapsack Problem | |
| |
| |
| |
A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem | |
| |
| |
Exercises | |
| |
| |
| |
Backtracking | |
| |
| |
| |
The Backtracking Technique | |
| |
| |
| |
The n-Queens Problem | |
| |
| |
| |
Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm | |
| |
| |
| |
The Sum-of-Subsets Problem | |
| |
| |
| |
Graph Coloring | |
| |
| |
| |
The Hamiltonian Circuits Problem | |
| |
| |
| |
The 0-1 Knapsack Problem | |
| |
| |
| |
A Backtracking Algorithm for the 0-1 Knapsack Problem | |
| |
| |
| |
Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem | |
| |
| |
Exercises | |
| |
| |
| |
Branch-and-Bound | |
| |
| |
| |
Illustrating Branch-and-Bound with the 0-1 Knapsack Problem | |
| |
| |
| |
Breadth-First Search with Branch-and-Bound Pruning | |
| |
| |
| |
Best-First Search with Branch-and-Bound Pruning | |
| |
| |
| |
The Traveling Salesperson Problem | |
| |
| |
| |
Abductive Inference (Diagnosis) | |
| |
| |
Exercises | |
| |
| |
| |
Introduction to Computational Complexity: The Sorting Problem | |
| |
| |
| |
Computational Complexity | |
| |
| |
| |
Insertion Sort and Selection Sort | |
| |
| |
| |
Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison | |
| |
| |
| |
Mergesort Revisited | |
| |
| |
| |
Quicksort Revisited | |
| |
| |
| |
Heapsort | |
| |
| |
| |
Heaps and Basic Heap Routines | |
| |
| |
| |
An Implementation of Heapsort | |
| |
| |
| |
Comparison of Mergesort, Quicksort, and Heapsort | |
| |
| |
| |
Lower Bounds for Sorting Only by Comparison of Keys | |
| |
| |
| |
Decision Trees for Sorting Algorithms | |
| |
| |
| |
Lower Bounds for Worst-Case Behavior | |
| |
| |
| |
Lower Bounds for Average-Case Behavior | |
| |
| |
| |
Sorting by Distribution (Radix Sort) | |
| |
| |
Exercises | |
| |
| |
| |
More Computational Complexity: The Searching Problem | |
| |
| |
| |
Lower Bounds for Searching Only by Comparisons of Keys | |
| |
| |
| |
Lower Bounds for Worst-Case Behavior | |
| |
| |
| |
Lower Bounds for Average-Case Behavior | |
| |
| |
| |
Interpolation Search | |
| |
| |
| |
Searching in Trees | |
| |
| |
| |
Binary Search Trees | |
| |
| |
| |
B-Trees | |
| |
| |
| |
Hashing | |
| |
| |
| |
The Selection Problem: Introduction to Adversary Arguments | |
| |
| |
| |
Finding the Largest Key | |
| |
| |
| |
Finding Both the Smallest and Largest Keys | |
| |
| |
| |
Finding the Second-Largest Key | |
| |
| |
| |
Finding the kth-Smallest Key | |
| |
| |
| |
A Probabilistic Algorithm for the Selection Problem | |
| |
| |
Exercises | |
| |
| |
| |
Computational Complexity and intractability: An Introduction to the Theory of NP | |
| |
| |
| |
Intractability | |
| |
| |
| |
Input Size Revisited | |
| |
| |
| |
The Three General Problems | |
| |
| |
| |
Problems for Which Polynomial-Time Algorithms Have Been Found | |
| |
| |
| |
Problems That Have Been Proven to Be Intractable | |
| |
| |
| |
Problems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found | |
| |
| |
| |
The Theory of NP | |
| |
| |
| |
The Sets P and NP | |
| |
| |
| |
NP-Complete Problems | |
| |
| |
| |
NP-Hard, NP-Easy, and NP-Equivalent Problems | |
| |
| |
| |
Handling NP-Hard Problems | |
| |
| |
| |
An Approximation Algorithm for the Traveling Salesperson Problem | |
| |
| |
| |
An Approximation Algorithm for the Bin-Packing Problem | |
| |
| |
Exercises | |
| |
| |
| |
Number-Theoretic Algorithms | |
| |
| |
| |
Number Theory Review | |
| |
| |
| |
Composite and Prime Numbers | |
| |
| |
| |
Greatest Common Divisor | |
| |
| |
| |
Prime Factorization | |
| |
| |
| |
Least Common Multiple | |
| |
| |
| |
Computing the Greatest Common Divisor | |
| |
| |
| |
Euclid's Algorithm | |
| |
| |
| |
An Extension to Euclid's Algorithm | |
| |
| |
| |
Modular Arithmetic Review | |
| |
| |
| |
Group Theory | |
| |
| |
| |
Congruency Modulo n | |
| |
| |
| |
Subgroups | |
| |
| |
| |
Solving Modular Linear Equations | |
| |
| |
| |
Computing Modular Powers | |
| |
| |
| |
Finding Large Prime Numbers | |
| |
| |
| |
Searching for a Large Prime | |
| |
| |
| |
Checking if a Number Is Prime | |
| |
| |
| |
The RSA Public-Key Cryptosystem | |
| |
| |
| |
Public-Key Cryptosystems | |
| |
| |
| |
The RSA Cryptosystem | |
| |
| |
Exercises | |
| |
| |
| |
Introduction to Parallel Algorithms | |
| |
| |
| |
Parallel Architectures | |
| |
| |
| |
Control Mechanism | |
| |
| |
| |
Address-Space Organization | |
| |
| |
| |
Interconnection Networks | |
| |
| |
| |
The PRAM Model | |
| |
| |
| |
Designing Algorithms for the CREW PRAM Model | |
| |
| |
| |
Designing Algorithms for the CRCW PRAM Model | |
| |
| |
Exercises | |
| |
| |
| |
Review of Necessary Mathematics | |
| |
| |
| |
Notation | |
| |
| |
| |
Functions | |
| |
| |
| |
Mathematical Induction | |
| |
| |
| |
Theorems and Lemmas | |
| |
| |
| |
Logarithms | |
| |
| |
| |
Definition and Properties of Logarithms | |
| |
| |
| |
The Natural Logarithm | |
| |
| |
| |
Sets | |
| |
| |
| |
Permutations and Combinations | |
| |
| |
| |
Probability | |
| |
| |
| |
Randomness | |
| |
| |
| |
The Expected Value | |
| |
| |
Exercises | |
| |
| |
| |
Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms | |
| |
| |
| |
Solving Recurrences Using Induction | |
| |
| |
| |
Solving Recurrences Using the Characteristic Equation | |
| |
| |
| |
Homogeneous Linear Recurrences | |
| |
| |
| |
Nonhomogeneous Linear Recurrences | |
| |
| |
| |
Change of Variables (Domain Transformations) | |
| |
| |
| |
Solving Recurrences by Substitution | |
| |
| |
| |
Extending Results for n, a Power of a Positive Constant b, to n in General | |
| |
| |
| |
Proofs of Theorems | |
| |
| |
Exercises | |
| |
| |
| |
Data Structures for Disjoint Sets | |
| |
| |
References | |
| |
| |
Index | |