Algorithms in a Nutshell A Practical Guide (George T. Heineman, Gary Pollice etc.) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 15.2 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

(This page has no text content)

📄 Page 3

Algorithms in a Nutshell SECOND EDITION George T. Heineman, Gary Pollice & Stanley Selkow

📄 Page 4

(This page has no text content)

📄 Page 5

Algorithms in a Nutshell by George T. Heineman, Gary Pollice, and Stanley Selkow Copyright © 2016 George Heineman, Gary Pollice and Stanley Selkow. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://safaribooksonline.com). For more information, contact our corporate/institutional sales department: 800-998-9938 or corporate@oreilly.com. Editors: Andy Oram and Mary Treseler Production Editor: Colleen Lobner Copyeditor: Christina Edwards Proofreader: Jasmine Kwityn Indexer: Judy McConville Interior Designer: David Futato Cover Designer: Karen Montgomery Illustrator: Rebecca Demarest October 2008: First Edition March 2016: Second Edition

📄 Page 6

Revision History for the Second Edition 2016-03-09: First Release See http://oreilly.com/catalog/errata.csp?isbn=9781491948927 for release details. Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trademarks of O’Reilly Media, Inc. Algorithms in a Nutshell, the cover image of a hermit crab, and related trade dress are trademarks of O’Reilly Media, Inc. While the publisher and the authors have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the authors disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights. 978-1-491-94892-7 [LSI]

📄 Page 7

(This page has no text content)

📄 Page 8

Preface to the Second Edition Revising a book for a new edition is always an arduous task. We wanted to make sure that we retained all the good qualities of the first edition, published in 2009, while fixing some of its shortcomings and adding additional material. We continue to follow the principles outlined in the first edition: Use real code, not just pseudocode to describe algorithms Separate the algorithm from the problem being solved Introduce just enough mathematics Support mathematical analysis empirically As we updated this second edition, we reduced the length of our text descriptions and simplified the layout to make room for new algorithms and additional material. We believe we continue to offer a Nutshell perspective on an important area of computer science that has significant impact on practical software systems.

📄 Page 9

Changes to the Second Edition In updating this book for the second edition, we followed these principles: Select New Algorithms After the publication of the first edition, we often received comments such as “Why was Merge Sort left out?” or “Why didn’t you cover Fast Fourier Transform (FFT)?” It was impossible to satisfy all of these requests, but we were able to add the following algorithms: Fortune’s algorithm, to compute the Voronoi Diagram for a set of points (“Voronoi Diagram”) Merge Sort, for both internal memory data as well as external files (“Merge Sort”) Multithreaded Quicksort (“Parallel Algorithms”) AVL Balanced Binary Tree implementation (“Solution”) A new Spatial Algorithms chapter (Chapter 10) contains R-Trees and Quadtrees In total, the book covers nearly 40 essential algorithms. Streamline Presentation To make room for the new material, we revised nearly every aspect of the first edition. We simplified the template used to describe each algorithm and reduced the accompanying descriptions. Add Python Implementations Rather than reimplement existing algorithms in Python, we intentionally used Python to implement most of the new algorithms added. Manage Code Resources The code for the first edition was made available as a ZIP file. We have since transitioned to a GitHub repository. Over the years we improved the quality of the code and its documentation. We have incorporated a number of blog entries that were written after the publication of the first edition. There are over 500 unit test cases and we use code coverage tools to ensure coverage of 99% of our Java code. In total, the code repository consists of over 110 KLOC.

📄 Page 10

Audience We intend this book to be your primary reference when seeking practical information on how to implement or use an algorithm. We cover a range of existing algorithms for solving a large number of problems and adhere to the following principles: When describing each algorithm, we use a stylized template to properly frame each discussion and explain the essential points of each algorithm We use a variety of languages to implement each algorithm (including C, C++, Java, and Python). In doing so, we make concrete the discussion of algorithms and speak using languages you are already familiar with We describe the expected performance of each algorithm and empirically provide evidence to support these claims We intend this book to be most useful to software practitioners, programmers, and designers. To meet your objectives, you need access to a quality resource that explains real solutions to practical algorithms you need to solve real problems. You already know how to program in a variety of programming languages. You know about the essential computer science data structures, such as arrays, linked lists, stacks, queues, hash tables, binary trees, and undirected and directed graphs. You don’t need to implement these data structures, since they are typically provided by code libraries. We expect you will use this book to learn about tried and tested solutions to solve problems efficiently. You will learn some advanced data structures and novel ways to apply standard data structures to improve the efficiency of algorithms. Your problem- solving abilities will improve when you see the key decision for each algorithm that make for efficient solutions.

📄 Page 11

Conventions Used in This Book The following typographical conventions are used in this book: Code All code examples appear in this typeface. This code is replicated directly from the code repository and reflects real code. All code listings are “pretty-printed” to highlight the appropriate syntax of the programming language. Italic Indicates key terms used to describe algorithms and data structures. Also used when referring to variables within a pseudocode description of an example. Constant width Indicates the name of actual software elements within an implementation, such as a Java class, the name of an array within a C implementation, and constants such as true or false. We cite numerous books, articles, and websites throughout the book. These citations appear in text using parentheses, such as (Cormen et al., 2009), and each chapter closes with a listing of references used within that chapter. When the reference citation immediately follows the name of the author in the text, we do not duplicate the name in the reference. Thus, we refer to the Art of Computer Programming books by Donald Knuth (1998) by just including the year in parentheses. All URLs used in the book were verified as of January 2016, and we tried to use only URLs that should be around for some time. We include small URLs, such as http://www.oreilly.com, directly within the text; otherwise, they appear in footnotes and within the references at the end of a chapter.

📄 Page 12

Using Code Examples Supplemental material (code examples, exercises, etc.) is available for download at https://github.com/heineman/algorithms-nutshell-2ed. This book is here to help you get your job done. In general, if example code is offered with this book, you may use it in your programs and documentation. You do not need to contact us for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing a CD-ROM of examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example code from this book into your product’s documentation does require permission. We appreciate, but do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “Algorithms in a Nutshell, Second Edition by George T. Heineman, Gary Pollice, and Stanley Selkow. Copyright 2016 George Heineman, Gary Pollice and Stanley Selkow, 978-1-4919-4892-7.” If you feel your use of code examples falls outside fair use or the permission given above, feel free to contact us at permissions@oreilly.com.

📄 Page 13

Safari® Books Online NOTE Safari Books Online is an on-demand digital library that delivers expert content in both book and video form from the world’s leading authors in technology and business. Technology professionals, software developers, web designers, and business and creative professionals use Safari Books Online as their primary resource for research, problem solving, learning, and certification training. Safari Books Online offers a range of plans and pricing for enterprise, government, education, and individuals. Members have access to thousands of books, training videos, and prepublication manuscripts in one fully searchable database from publishers like O’Reilly Media, Prentice Hall Professional, Addison-Wesley Professional, Microsoft Press, Sams, Que, Peachpit Press, Focal Press, Cisco Press, John Wiley & Sons, Syngress, Morgan Kaufmann, IBM Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders, McGraw-Hill, Jones & Bartlett, Course Technology, and hundreds more. For more information about Safari Books Online, please visit us online.

📄 Page 14

How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 800-998-9938 (in the United States or Canada) 707-829-0515 (international or local) 707-829-0104 (fax) We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at http://bit.ly/algorithms_nutshell_2e. To comment or ask technical questions about this book, send email to bookquestions@oreilly.com. For more information about our books, courses, conferences, and news, see our website at http://www.oreilly.com. Find us on Facebook: http://facebook.com/oreilly Follow us on Twitter: http://twitter.com/oreillymedia Watch us on YouTube: http://www.youtube.com/oreillymedia

📄 Page 15

Acknowledgments We would like to thank the book reviewers for their attention to detail and suggestions, which improved the presentation and removed defects from earlier drafts: From the first edition: Alan Davidson, Scot Drysdale, Krzysztof Duleba, Gene Hughes, Murali Mani, Jeffrey Yasskin, and Daniel Yoo. For the second edition: Alan Solis, Robert P. J. Day, and Scot Drysdale. George Heineman would like to thank those who helped instill in him a passion for algorithms, including Professors Scot Drysdale (Dartmouth College) and Zvi Galil (Columbia University, now Dean of Computing at Georgia Tech). As always, George thanks his wife, Jennifer, and his children Nicholas (who has now started learning how to program) and Alexander (who loves making origami creations from the printed rough drafts of this edition). Gary Pollice would like to thank his wife Vikki for 46 great years. He also wants to thank the WPI computer science department for a great environment and a great job. Stanley Selkow would like to thank his wife, Deb. This book was another step on their long path together.

📄 Page 16

(This page has no text content)

📄 Page 17

Chapter 1. Thinking in Algorithms Algorithms matter! Knowing which algorithm to apply under which set of circumstances can make a big difference in the software you produce. Let this book be your guide to learning about a number of important algorithm domains, such as sorting and searching. We will introduce a number of general approaches used by algorithms to solve problems, such as the Divide and Conquer or Greedy strategy. You will be able to apply this knowledge to improve the efficiency of your own software. Data structures have been tightly tied to algorithms since the dawn of computing. In this book, you will learn the fundamental data structures used to properly represent information for efficient processing. What do you need to do when choosing an algorithm? We’ll explore that in the following sections.

📄 Page 18

Understand the Problem The first step in designing an algorithm is to understand the problem you want to solve. Let’s start with a sample problem from the field of computational geometry. Given a set of points, P, in a two-dimensional plane, such as shown in Figure 1-1, picture a rubberband that has been stretched around the points and released. The resulting shape is known as the convex hull (i.e., the smallest convex shape that fully encloses all points in P). Your task is to write an algorithm to compute the convex hull from a set of two-dimensional points. Given a convex hull for P, any line segment drawn between any two points in P lies totally within the hull. Let’s assume we order the points in the hull clockwise. Thus, the hull is formed by a clockwise ordering of h points L0, L1, … ,Lh-1 as shown in Figure 1-2. Each sequence of three hull points Li, Li+1, Li+2 creates a right turn. Figure 1-1. Sample set of 15 points in plane

📄 Page 19

Figure 1-2. Computed convex hull for points With just this information, you can probably draw the convex hull for any set of points, but could you come up with an algorithm (i.e., a step-by-step sequence of instructions that will efficiently compute the convex hull for any set of points)? What we find interesting about the convex hull problem is that it doesn’t seem to be easily classified into existing algorithmic domains. There doesn’t seem to be any linear sorting of the points from left to right, although the points are ordered in clockwise fashion around the hull. Similarly, there is no obvious search being performed, although you can identify a line segment on the hull because the remaining n – 2 points are “to the right” of that line segment in the plane.

📄 Page 20

Naïve Solution Clearly a convex hull exists for any collection of three or more points. But how do you construct one? Consider the following idea. Select any three points from the original collection and form a triangle. If any of the remaining n – 3 points are contained within this triangle, then they cannot be part of the convex hull. We’ll describe the general process using pseudocode, and you will find similar descriptions for each of the algorithms in the book. SLOW HULL SUMMARY Best, Average, Worst: O(n4) slowHull (P) foreach p0 in P do foreach p1 in {P-p0} do foreach p2 in {P-p0-p1} do foreach p3 in {P-p0-p1-p2} do if p3 is contained within Triangle(p0,p1,p2) then mark p3 as internal create array A with all non-internal points in P determine leftmost point, left, in A sort A by angle formed with vertical line through left return A Points p0, p1, p2 form a triangle. Points not marked as internal are on convex hull. These angles (in degrees) range from –90 to 90. In the next chapter, we will explain the mathematical analysis that shows why this approach is considered to be inefficient. This pseudocode summary explains the steps that produce a convex hull for each input set; in particular, it created the convex hull in Figure 1-2. Is this the best we can do?