![](https://csdnimg.cn/release/download_crawler_static/11057716/bg11.jpg)
world (www.top500.org), and smaller versions of such machines being exploited in
many research laboratories. Therefore, the time is right to teach a fundamental
course in algorithms that covers paradigms for both sequential and parallel models.
The approach we take in this book is to integrate the presentation of sequential
and parallel algorithms. Specifically, we employ a philosophy of presenting a par-
adigm, such as divide-and-conquer, and then discussing implementation issues for
both sequential and parallel models. Due to the fact that we present design and
analysis of paradigms for sequential and parallel models, the reader might notice
that the number of paradigms we can treat within a semester is limited when com-
pared to a traditional sequential algorithms text.
This book has been used successfully at a wide variety of colleges and
universities.
Prerequisites: We assume a basic knowledge of data structures and mathemati-
cal maturity. The reader should be comfortable with notions of a stack, queue, list,
and binary tree, at a level that is typically taught in a CS2 course. The reader should
also be familiar with fundamentals of discrete mathematics and Calculus. Specifi-
cally, the reader should be comfortable with limits, summations, and integrals.
Overview of Chapters
Background material for the course is presented in Chapters 1, 2, and 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 funda-
mental material from a Freshman-level Calculus sequence might want to brush up
on notions such as limits, summations and integrals, and derivatives, as they natu-
rally 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 net-
works. 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 par-
allel models introduced include the PRAM, mesh, hypercube, and the Coarse-
Grained Multicomputer, to name a few. In addition, Chapter 5 introduces
terminology such as shared-memory and distributed-memory.
xvi Preface