Algorithms

Algorithms

Filling the void left by other algorithms books, Algorithms and Data Structures provides 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. Algorithms is written for an introductory upper-level undergraduate or graduate course in algorithms. With/their many years of experience in teaching algorithms courses, Richard Johnsonbaugh and Marcus Schaefer include applications of algorithms, examples, end-of-section exercises, end-of-chapter exercises, solutions to selected exercises, and notes to help the reader understand and master algorithms. Key Features Links theory to real-world applications such as data compression, region-finding in digital pictures, cellular phone networks, and the implementation of agrep. - Includes five chapters that emphasize design techniques: searching (including backtracking), divide and conquer, sorting, selection, the greedy method, and dynamic programming. - Covers distributed algorithms—a topic recommended by the ACM (2001 report) for an undergraduate curriculum. - Features a collection of techniques, including approximation, parameterization (a recent area of research), and use of heuristics, to deal with NP-complete problems. - Contains more than 1450 carefully developed and classroom-tested exercises, from routine to challenging. About one-third of the end-of-section exercises include solutions. - Provides a robust Companion Website that supplements the text by providing algorithm simulation software, PowerPoint ® slides, late breaking news about algorithms, references about the book's topics, computer programs, and more. - Includes more than 300 worked examples, which provide motivation, clarify concepts, and show how to develop algorithms, demonstrate applications of the theory, and elucidate proofs. Richard Johnsonbaugh is Professor Emeritus of Computer Science at DePaul University. He has degrees in computer science and mathematics from the University of Oregon, Yale University, and the University of Illinois at Chicago. He is the author of numerous articles and books, including Discrete Mathematics, Fifth Edition, and, with co-author Martin Kalin, Object-Oriented Programming in C++, Second Edition, Applications Programming in C++, and Applications Programming in ANSI C, Third Edition. Marcus Schaefer is Assistant Professor of Computer Science at DePaul University. He holds degrees in computer science and mathematics from the University of Chicago and the Universitat Karlsruhe. He has authored and co-authored several articles on complexity theory, computability, and graph theory. Why We Wrote This Book Intended 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 on NP -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 (S