Foundations of algorithms / Richard E. Neapolitan, PhD, Northwestern University.

Includes bibliographical references (pages 653-658) and index.

Machine generated contents note: 1. Algorithms: Efficiency, Analysis, and Order -- 1.1. Algorithms -- 1.2. The Importance of Developing Efficient Algorithms -- 1.2.1. Sequential Search Versus Binary Search -- 1.2.2. The Fibonacci Sequence -- 1.3. Analysis of Algorithms -- 1.3.1. Complexity Analysis -- 1.3.2. Applying the Theory -- 1.3.3. Analysis of Correctness -- 1.4. Order -- 1.4.1. An Intuitive Introduction to Order -- 1.4.2. A Rigorous Introduction to Order -- 1.4.3. Using a Limit to Determine Order -- 1.5. Outline of This Book -- Exercises -- 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.6.1. Representation of Large Integers: Addition and Other Linear-Time Operations.

2.6.2. Multiplication of Large Integers -- 2.7. Determining Thresholds -- 2.8. When Not to Use Divide-and-Conquer -- Exercises -- 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 -- 3.7. Sequence Alignment -- Exercises -- 4. The Greedy Approach -- 4.1. Minimum Spanning Trees -- 4.1.1. Prim's Algorithm -- 4.1.2. Kruskal's Algorithm -- 4.1.3. Comparing Prim's Algorithm with Kruskal's Algorithm -- 4.1.4. Final Discussion -- 4.2. Dijkstra's Algorithm for Single-Source Shortest Paths -- 4.3. Scheduling -- 4.3.1. Minimizing Total Time in the System -- 4.3.2. Scheduling with Deadlines -- 4.4. Huffman Code -- 4.4.1. Prefix Codes -- 4.4.2. Huffman's Algorithm -- 4.5. The Greedy Approach versus Dynamic Programming: The Knapsack Problem.

4.5.1. A Greedy Approach to the 0-1 Knapsack Problem -- 4.5.2. A Greedy Approach to the Fractional Knapsack Problem -- 4.5.3. A Dynamic Programming Approach to the 0-1 Knapsack Problem -- 4.5.4. A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem -- Exercises -- 5. Backtracking -- 5.1. The Backtracking Technique -- 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 -- 5.7.1. A Backtracking Algorithm for the 0-1 Knapsack Problem -- 5.7.2. Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem -- Exercises -- 6. Branch-and-Bound -- 6.1. Illustrating Branch-and-Bound with the 0-1 Knapsack Problem -- 6.1.1. Breadth-First Search with Branch-and-Bound Pruning -- 6.1.2. Best-First Search with Branch-and-Bound Pruning.

6.2. The Traveling Salesperson Problem -- 6.3. Abductive Inference (Diagnosis) -- Exercises -- 7. Introduction to Computational Complexity: The Sorting Problem -- 7.1. Computational Complexity -- 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 -- 8. More Computational Complexity: The Searching Problem -- 8.1. Lower Bounds for Searching Only by Comparisons of Keys -- 8.1.1. Lower Bounds for Worst-Case Behavior.

8.1.2. Lower Bounds for Average-Case Behavior -- 8.2. Interpolation Search -- 8.3. Searching in Trees -- 8.3.1. Binary Search Trees -- 8.3.2. B-Trees -- 8.4. Hashing -- 8.5. The Selection Problem: Introduction to Adversary Arguments -- 8.5.1. Finding the Largest Key -- 8.5.2. Finding Both the Smallest and Largest Keys -- 8.5.3. Finding the Second-Largest Key -- 8.5.4. Finding the kth-Smallest Key -- 8.5.5. A Probabilistic Algorithm for the Selection Problem -- Exercises -- 9. Computational Complexity and Intractability: An Introduction to the Theory of NP -- 9.1. Intractability -- 9.2. Input Size Revisited -- 9.3. The Three General Problem Categories -- 9.3.1. Problems for Which Polynomial-Time Algorithms Have Been Found -- 9.3.2. Problems That Have Been Proven to Be Intractable -- 9.3.3. Problems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found -- 9.4. The Theory of NP

9.4.1. The Sets P and NP -- 9.4.2. NP-Complete Problems -- 9.4.3. NP-Hard, NP-Easy, and NP-Equivalent Problems -- 9.5. Handling NP-Hard Problems -- 9.5.1. An Approximation Algorithm for the Traveling Salesperson Problem -- 9.5.2. An Approximation Algorithm for the Bin-Packing Problem -- Exercises -- 10. Genetic Algorithms and Genetic Programming -- 10.1. Genetics Review -- 10.2. Genetic Algorithms -- 10.2.1. Algorithm -- 10.2.2. Illustrative Example -- 10.2.3. The Traveling Salesperson Problem -- 10.3. Genetic Programming -- 10.3.1. Illustrative Example -- 10.3.2. Artificial Ant -- 10.3.3. Application to Financial Trading -- 10.4. Discussion and Further Reading -- Exercises -- 11. Number-Theoretic Algorithms -- 11.1. Number Theory Review -- 11.1.1. Composite and Prime Numbers -- 11.1.2. Greatest Common Divisor -- 11.1.3. Prime Factorization -- 11.1.4. Least Common Multiple -- 11.2. Computing the Greatest Common Divisor.

11.2.1. Euclid's Algorithm -- 11.2.2. An Extension to Euclid's Algorithm -- 11.3. Modular Arithmetic Review -- 11.3.1. Group Theory -- 11.3.2. Congruency Modulo n -- 11.3.3. Subgroups -- 11.4. Solving Modular Linear Equations -- 11.5. Computing Modular Powers -- 11.6. Finding Large Prime Numbers -- 11.6.1. Searching for a Large Prime -- 11.6.2. Checking if a Number Is Prime -- 11.7. The RSA Public-Key Cryptosystem -- 11.7.1. Public-Key Cryptosystems -- 11.7.2. The RSA Cryptosystem -- Exercises -- 12. Introduction to Parallel Algorithms -- 12.1. Parallel Architectures -- 12.1.1. Control Mechanism -- 12.1.2. Address-Space Organization -- 12.1.3. Interconnection Networks -- 12.2. The PRAM Model -- 12.2.1. Designing Algorithms for the CREW PRAM Model -- 12.2.2. Designing Algorithms for the CRCW PRAM Model -- Exercises -- Appendix A Review of Necessary Mathematics -- A.1. Notation -- A.2. Functions -- A.3. Mathematical Induction.

A.4. Theorems and Lemmas -- A.5. Logarithms -- A.5.1. Definition and Properties of Logarithms -- A.5.2. The Natural Logarithm -- A.6. Sets -- A.7. Permutations and Combinations -- A.8. Probability -- A.8.1. Randomness -- A.8.2. The Expected Value -- Exercises -- Appendix B Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms -- B.1. Solving Recurrences Using Induction -- B.2. Solving Recurrences Using the Characteristic Equation -- B.2.1. Homogeneous Linear Recurrences -- B.2.2. Nonhomogeneous Linear Recurrences -- B.2.3. Change of Variables (Domain Transformations) -- 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.