Title:
Foundations of algorithms
Author:
Neapolitan, Richard E., author.
ISBN:
9781284049190
Personal Author:
Edition:
Fifth edition.
Physical Description:
xvii, 676 pages ; 24 cm
Contents:
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 Integers -- 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 Problem Categories -- 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 -- Genetic Algorithms and Genetic Programming -- Genetics Review -- Genetic Algorithms -- Algorithm -- Illustrative Example -- The Traveling Salesperson Problem -- Genetic Programming -- Illustrative Example -- Artificial Ant -- Application to Financial Trading -- Discussion and Further Reading -- 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.