Algorithms Sequential and Parallel

Background material for the course is presented in Chapters 1, 2, & 3. Chapter 1 introduces the concept of asymptotic analysis. While the reader might have seen some of this material in a course on data structures, we present this material in a fair amount of detail. The reader who is uncomfortable with some of the fundamental material from a Freshman-level Calculus sequence might want to brush up on notions such as limits, summations and integrals, and derivatives, as they naturally arise in the presentation and application of asymptotic analysis. Chapter 2 focuses on fundamentals of induction and recursion. While many students have seen this material in previous courses in computer science and/or mathematics, we have found it important to review this material briefly and to provide the students with a reference for performing the necessary review. In Chapter 3, we present the Master Method, a very useful cookbook-type of system for evaluating recurrence equations that are common in an algorithms-based setting.

Chapter 4 presents an overview of combinational circuits and sorting networks. This work is used to motivate the natural use of parallel models and to demonstrate the blending of architectural and algorithmic approaches. In Chapter 5, we introduce fundamental models of computation, including the RAM (a formal sequential architecture) and a variety of parallel models of computation. The parallel models introduced include the PRAM, mesh, and hypercube, to name a few. In addition, Chapter 5 introduces terminology such as shared-memory and distributed memory.

The focus of Chapter 6 is the important problem of matrix multiplication, which is considered for a variety of models of computation. In Chapter 7, we introduce the parallel prefix operation. This is a very powerful operation with a wide variety of applications. We discuss implementations and analysis for a number of the models presented in Chapter 5 and give sample applications. In Chapter 8, we introduce pointer jumping techniques and show how some list-based algorithms can be efficiently implemented in parallel.

In Chapter 9, we introduce the powerful divide-and-conquer paradigm. We discuss applications of divide-and-conquer to problems involving data movement, including sorting, concurrent reads/writes, and so forth. Algorithms and their analysis are presented for a variety of models.

Chapters 10 & 11 focus on two important application areas, namely, computational geometry and image processing. In these chapters, we focus on interesting problems chosen from these important domains as a way of solidifying the approach of this book in terms of developing machine independent solution strategies, which can then be tailored for specific models, as required.

Chapter 12 focuses on fundamental graph theoretic problems. Initially, we present standard traversal techniques, including breadth-first search, depth-first search, and pointer jumping. We then discuss fundamental problems, including tree contraction and transitive closure. Finally, we couple these techniques with greedy algorithms to solve problems, such as labeling the connected components of a graph, determining a minimal spanning forest of a graph, and problems involving shortest or minimal-weight paths in a graph.

Chapter 13 is an optional chapter concerned with some fundamental numerical problems. The focus of the chapter is on sequential algorithms for polynomial evaluation and approximations of definite integrals.