Algorithms

by Johnsonbaugh, Richard; Schaefer, Marcus

• ISBN13: 9780023606922
• ISBN10: 0023606924
• Edition: 1st
• Format: Hardcover
• Copyright: 2003-07-31
• Publisher: Pearson

Summary

Filling the void left by other algorithms books,Algorithms and Data Structuresprovides an approach that emphasizes design techniques. The volume includes application of algorithms, examples, end-of-section exercises, end-of-chapter exercises, hints and solutions to selected exercises, figures and notes to help the reader master the design and analysis of algorithms.This volume covers data structures, searching techniques, divided-and-conquer sorting and selection, greedy algorithms, dynamic programming, text searching, computational algebra, P and NP and parallel algorithms.For those interested in a better understanding of algorithms.

Author Biography

Marcus Schaefer is Assistant Professor of Computer Science at DePaul University. Richard Johnsonbaugh is Professor Emeritus of Computer Science at DePaul University.

Table of Contents

Preface	ix
Introduction	1	(16)
Algorithms	1	(3)
Pseudocode for Algorithms	4	(6)
The Present	10	(2)
The Future	12	(5)
Notes	14	(1)
Chapter Exercises	14	(3)
Mathematics for Algorithms	17	(82)
Definitions, Notation, and Basic Results	17	(15)
Mathematical Induction	32	(9)
Analysis of Algorithms	41	(14)
Recurrence Relations	55	(13)
Graphs	68	(18)
Trees	86	(13)
Notes	94	(1)
Chapter Exercises	94	(5)
Data Structures	99	(66)
Abstract Data Types	99	(2)
Stacks and Queues	101	(10)
Linked Lists	111	(9)
Binary Trees	120	(13)
Priority Queues, Binary Heaps, and Heapsort	133	(17)
Disjoint Sets	150	(15)
Notes	162	(1)
Chapter Exercises	162	(3)
Searching	165	(48)
Binary Search	165	(7)
Depth-First Search	172	(9)
Breadth-First Search	181	(7)
Topological Sort	188	(7)
Backtracking	195	(18)
Notes	209	(1)
Chapter Exercises	209	(4)
Divide and Conquer	213	(26)
A Tiling Problem	213	(6)
Mergesort	219	(6)
Finding a Closest Pair of Points	225	(7)
Strassen's Matrix Product Algorithm	232	(7)
Notes	236	(1)
Chapter Exercises	236	(3)
Sorting and Selection	239	(32)
Insertion Sort	239	(4)
Quicksort	243	(11)
A Lower Bound for the Sorting Problem	254	(3)
Counting Sort and Radix Sort	257	(5)
Selection	262	(9)
Notes	268	(1)
Chapter Exercises	268	(3)
Greedy Algorithms	271	(52)
Coin Changing	271	(4)
Kruskal's Algorithm	275	(9)
Prim's Algorithm	284	(11)
Dijkstra's Algorithm	295	(7)
Huffman Codes	302	(11)
The Continuous-Knapsack Problem	313	(10)
Notes	319	(1)
Chapter Exercises	319	(4)
Dynamic Programming	323	(44)
Computing Fibonacci Numbers	323	(5)
Coin Changing Revisited	328	(8)
Multiplying Matrices	336	(6)
The Longest-Common-Subsequence Problem	342	(8)
The Algorithms of Floyd and Warshall	350	(17)
Notes	361	(1)
Chapter Exercises	361	(6)
Text Searching	367	(62)
Simple Text Search	368	(3)
The Rabin-Karp Algorithm	371	(8)
The Knuth-Morris-Pratt Algorithm	379	(13)
The Boyer-Moore-Horspool Algorithm	392	(6)
Approximate Pattern Matching	398	(10)
Regular Expression Matching	408	(21)
Notes	422	(1)
Chapter Exercises	423	(6)
P and NP	429	(64)
Polynomial Time	429	(8)
Nondeterministic Algorithms and NP	437	(15)
Reducibility and NP-Completeness	452	(14)
NP-Complete Problems	466	(8)
More on NP-Completeness	474	(19)
Notes	481	(1)
Chapter Exercises	482	(11)
Coping with NP-Completeness	493	(66)
Brute Force	495	(9)
Randomness	504	(7)
Approximation	511	(15)
Parameterization	526	(15)
Heuristics	541	(18)
Notes	551	(1)
Chapter Exercises	552	(7)
Parallel and Distributed Algorithms	559	(86)
Introduction	559	(4)
The Parallel Random Access Machine (PRAM)	563	(24)
Sorting Networks	587	(17)
Parallel Architectures	604	(22)
Distributed Algorithms	626	(19)
Notes	639	(1)
Chapter Exercises	640	(5)
References	645	(6)
Solutions to Selected Exercises	651	(84)
Index	735

Excerpts

Why We Wrote This BookIntended for an upper-level undergraduate or graduate course in algorithms, this book is based on our combined 25 years of experience in teaching this course. Our major goals in writing this book were to Emphasize design techniques. Show that algorithms are fun and exciting. Include real-world applications. Provide numerous worked examples and exercises.Faced with a new computational problem, a designer will often be able to solve it by using one of the algorithms in this book, perhaps after modifying or adapting it slightly. However, some problems cannot be solved by any of the algorithms in this book. For this reason, we present a repertoire of design techniques that can be used to solve the problem and help the reader to develop intuition about which techniques are likely to succeed. The chapters onNP-completeness and how to deal with it also tell how to recognize problems that are hard to solve and which techniques are available in that case.Working with algorithms should be fun and exciting. The design of algorithms is a creative task requiring the solution of new problems and old problems in disguise. To be successful, we believe that it is important to enjoy the challenge that a new problem poses. To this end, we have included more examples and exercises of a combinatorial and recreational nature than is typical for a book of this type. All too often the challenge of an unsolved problem is experienced as a threat rather than as an opportunity, and we hope that these examples and exercises help to remove the threat.Examples of real-word applications of algorithms in this book include data compression in Section 7.5, and the Boyer-Moore-Horspool algorithm in Section 9.4, which is used as part of the implementation of agrep. Most sections of the book introduce a motivating example in the first paragraph. The closest-pair problem (Section 5.3) begins with a pattern recognition example, and Section 8.4, which is concerned with the longest-common-subsequence problem, begins with a discussion of the analysis of proteins.Algorithm design and analysis are best learned by experience. For this reason, we provide large numbers of worked examples and exercises. Worked examples show how to deal with algorithms, and exercises let the reader practice the techniques. There are over 300 worked examples throughout the book. These examples clarify and show how to develop algorithms, demonstrate applications of the theory, elucidate proofs, and help to motivate the material. The book contains over 1450 exercises, from routine to challenging, which were carefully developed through classroom testing. Close attention was paid to clarity and precision. Because some instant feedback is essential for students, we provide answers to about one-third of the end-of-section exercises (marked with "S" in the exercises) in the back of the book. Solutions to the remaining end-of-section exercises are reserved for instructors (see the Instructor Supplement section that follows). PrerequisitesThe principal computer science prerequisite is a data structures course that covers stacks, queues, linked lists, trees, and graphs. A course in discrete mathematics that covers logic, asymptotic notation (e.g., "big oh" notation), and recurrence relations and their solution by iteration is the main mathematics prerequisite. We do not use advanced methods such as generating functions. In one or two places, we use some basic concepts from calculus. The mathematics topics and data structures used in this book are summarized in Chapters 2 and 3. Some or all of these chapters can be used for reference or review or incorporated into an algorithms course as needed. ContentFollowing the first three chapters (containing an introduction, mathematics topics, and data structures), the book presents five chapters that emphasize design techniq