Computational Complexity of Sequential and Parallel Algorithms

Cover
Title page
Preface
Part One Sequential Algorithms
1. Introduction
1.1 Measures of Complexity
1.2 Computer Model
2. Arithmetic Complexity of Computations
2.1 Discoveries of the 1960s
2.2 Product of Integers
2.3 The Fast Fourier Transform (FIT)
2.4 Matrix Product
2.5 Summary
3. Solving Recurrence Relations
3.1 Divide-and-conquer Approach
3.2 Technique of Recurrence Expansion
3.3 Solution of Homogeneous Recurrences
3.4 Homogeneous Equations
3.5 Non-homogeneous Equations
3.6 Transformation Techniques
3.7 Guessing a Solution
4. Complexity of Data-processing Problems
4.1 Worst-case and Average-case Time Bounds
4.2 Data Structures
4.3 Comments
5. Complexity and Difficult Combinatorial Problems
5.1 Exponential Time Algorithms
5.2 Efficient Algorithm Design Techniques
5.3 Probabilistic Algorithms
6. Complexity and Theorem Proving by Machine
6.1 The First-order Integer Addition Problem
6.2 Decidable and Undecidable Problems
6.3 Decidable Problems and their Algorithms
6.4 Diagonalization and Reduction
6.5 Lower Bounds
7. Classifying the Computational Complexity of Algorithms
7.1 Terminology and Notation
7.2 Non-deterministic Algorithms
7.3 NP-complete Problems
7.4 Khachian's Algorithm
7.5 Beyond the NP-c1ass
8. The Theory of Computational Complexity
8.1 Some Basic Definitions
8.2 Theoretical Complexity Measures and Related Results
8.3 The Speed-up Theorem
8.4 Complexity Classes. The Gap Theorem
Part Two Parallel Algorithms
9. Computational Complexity of Parallel Algorithms
9.1 Introduction
9.2 Parallel Computers
9.3 Parallel Algorithms
9.4 Cascade Partial Sum Method
10. The Root-finding Aigorithms for a Non-linear Function
10.1 ParaUel Zero-searching Algorithms
11. Iterative Parallel Algorithms
11.1 Models of Parallel Iterative Methods
11.2 Model for a Performance Analysis of a Synchronized Iterative Algorithm
11.3 Asynchronous Iterative Algorithms
11.4 Parallel Algorithms for Solving Systems of Non-linear Equations
12. Synchronized Matrix Multiplication Algorithms
12.1 Matrix Multiplication Algorithms
12.2 Parallel Hardware Considerations for the Matrix Product Algorithms
12.3 Conc1uding Remarks
13. The Parallel FFT Algorithm
13.1 Bergland's ParaUel FIT Algorithm
13.2 Parallel Radix-2 FIT Computation
13.3 Parallel Computation of the Two-dimensional DFT
14. Parallel Comparison Sorts
14.1 Lower Bounds on Parallel Comparison Problems
14.2 Enumeration Sorting
14.3 Odd-even Transposition Sort
14.4 Bucket (Distribution) Sorts
14.5 Merge Sorts
15. Parallel Graph Search and Traversal
15.1 Distributed Computing Systems (DCS) Graphs
15.2 Parallel Graph Algorithms
15.3 Parallel Topological Sort
Index