Foundations of algorithms

Responsibility Richard E. Neapolitan, PhD (Northwestern University). Edition Fifth edition. Publication Burlington, MA : Jones & Bartlett Learning, [2015] Copyright notice ©2015 Physical description xvii, 676 pages : illustrations ; 24 cm

Online

Available online

At the library

Science Library (Li and Ma)

Stacks

Items in Stacks

Call number	Note	Status
QA9.58 .N43 2015	Unknown

More options

Top
Contributors
Summary
Subjects
Info
Browse
Bottom

Description

Creators/Contributors

Author/Creator Neapolitan, Richard E., author.

Contents/Summary

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.

Subjects

Bibliographic information

Publication date 2015 Copyright date 2015 ISBN 9781284049190 (pbk.) 1284049191 (pbk.)