Algorithms : Sequential , Parallel , and Distributed (Hardcover)

Kenneth A. Berman, Jerome L. Paul




Algorithms: Sequential, Parallel, and Distributed provides in-depth coverage of traditional and current topics in sequential algorithms, as well as providing a solid introduction to the theory of parallel and distributed algorithms. In light of the emergence of modern computing environments such as parallel computers, the Internet, cluster and grid computing, it is important that majors in computer science and related disciplines be exposed to algorithms that exploit these technologies. Professors Berman and Paul give students a comprehensive toolkit of sequential, parallel and distributed algorithms plus a set of mathematical techniques for assessing the performance and correctness of algorithms. These tools enable the reader to choose the best algorithm to use in a given circumstance from amongst several algorithms that might be available for the problem.


Table of Contents:

Part 1: Introduction to Algorithms
1. Introduction to Preliminaries
2. Design and Analysis Fundamentals
3. Mathematical Tools for Algorithm Analysis
4. Trees and Applications to Algorithms
5. More on Sorting Algorithms
6. Probability and Average Complexity of Algorithms
Part 2: Major Design Strategies
7. The Greedy Method
8. Divide-and-Conquer
9. Dynamic Programming
10. Backtracking and Branch-and-Bound
Part 3: Graph and Network Algorithms
11. Graphs and Digraphs
12. Minimum Spanning Tree and Shortest-Path Algorithms
13. Graph Connectivity and Fault-Tolerance of Networks
14. Matching and Network Flow Algorithms
Part 4: Parallel and Distributed Algorithms
15. Introduction to Parallel Algorithms and Architectures
16. Parallel Design Strategies
17. Internet Algorithms
18. Distributed Computation Algorithms
19. Distributed Network Algorithms
Part 5: Special Topics
20. String Matching and Document Processing
21. Balanced Search Trees
22. The Fast Fourier Transform
23. Heuristic Search Strategies: A*-Search and Game Trees
24. Probabilistic and Randomized Algorithms
25. Lower-Bound Theory
26. NP-Complete Problems
27. Approximation Algorithms
A: Mathematical Notation and Background
B: Linear Data Structures
C: Interpolating Asympotic Behavior
D: Random Walks in Digraphs
E: Elementary Probability Theory
F: Examples of Message-Passing Interface Code
G: Pseudocode Conventions