TY  - BOOK
AU  - Neapolitan,Richard E.
TI  - Foundations of algorithms
SN  - 9781284049190 (paperback)
PY  - 2015///]
CY  - Burlington, MA
PB  - Jones & Bartlett Learning
KW  - Algorithms
KW  - Constructive mathematics
KW  - Computational complexity
N1  - 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
ER  -