George Heineman - Learning Algorithms

by George T. Heineman

Copyright 2021 George T. Heineman. All rights reserved.

Printed in the United States of America.

Published by OReilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472.

OReilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://oreilly.com). For more information, contact our corporate/institutional sales department: 800-998-9938 or corporate@oreilly.com .

• Acquisitions Editor: Melissa Duffield
• Developmental Editor: Sarah Grey
• Production Editor: Beth Kelly
• Copyeditor: Piper Editorial Consulting, LLC
• Proofreader: Justin Billing
• Indexer: nSight, Inc.
• Interior Designer: David Futato
• Cover Designer: Karen Montgomery
• Illustrator: Kate Dullea

• August 2021: First Edition

See http://oreilly.com/catalog/errata.csp?isbn=9781492091066 for release details.

The OReilly logo is a registered trademark of OReilly Media, Inc. Learning Algorithms, the cover image, and related trade dress are trademarks of OReilly Media, Inc.

The views expressed in this work are those of the author, and do not represent the publishers views. While the publisher and the author have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the author 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-492-09106-6

[GP]

Algorithms are at the heart of computer science and essential to the modern information age. They power the search engines used to answer billions of daily Internet search requests and provide privacy when communicating over the Internet. Algorithms are increasingly visible to consumers in countless areas, from customized advertising to online price quotes, and the news media is full of discussions about what algorithms are and what they can do.

The large growth in STEM (Science, Technology, Engineering and Mathematics) is powering a new wave of sustained growth and innovation in the global economy. But there simply arent enough computer scientists to discover and apply the algorithms needed for advances in medicine, engineering, and even government. We need to increase the number of people who know how to apply algorithms to the problems within their own fields and disciplines.

You dont need a four-year degree in computer science to get started with algorithms. Unfortunately, most online material and textbooks on the topic are designed for undergraduate students, with an emphasis on mathematical proofs and computer science concepts. Algorithm textbooks can be intimidating because they are references for so many different algorithms, with countless variations and highly specialized cases. All too often, readers find it hard to complete the first chapter of these books. Using them can be a bit like trying to improve your English spelling by reading an entire dictionary: you would be much better off if, instead, you had a specially designed reference book that summarizes the 100 most misspelled words in the English language and explains the rules (and exceptions) that govern them. Similarly, people from different backgrounds and experiences who use algorithms in their work need a reference book that is more focused and designed for their needs.

Learning Algorithms provides an approachable introduction to a range of algorithms that you can immediately use to improve the efficiency of your code. All algorithms are presented in Python, one of the most popular and user-friendly programming languages, used in disciplines ranging from data science to bioinformatics to engineering. The text carefully explains each algorithm, with numerous images to help readers grasp the essential concepts. The code is open source and freely available from the books repository.

Learning Algorithms will teach you the fundamental algorithms and data types used in computer science, so that you can write more efficient programs. If you are looking for a technical job that requires programming skills, this book might help you ace your next coding interview. I hope it inspires you to continue your journey in learning algorithms.

Zvi Galil

Dean of Computing Emeritus

Frederick G. Storey Chair in Computing

Georgia Institute of Technology

Atlanta, May 2021

Preface

Who This Book Is For

If you are reading this book, I assume you already have a working knowledgeof a programming language, such as Python. If you have never programmedbefore, I encourage you to first learn a programming language and then comeback! I use Python in this book because it is accessible to programmers andnonprogrammers alike.

Algorithms are designed to solve common problems that arise frequently insoftware applications. When teaching algorithms to undergraduate students,I try to bridge the gap between the students background knowledge and thealgorithm concepts Im teaching. Many textbooks have carefully writtenbutalways too briefexplanations. Without having a guide to explain how tonavigate this material, students are often unable to learn algorithms ontheir own.

In one paragraph and in , let me show you my goal for the book. I introduce a number of data structures that explain how to organize information using primitive fixed-size types, such as 32-bit integer values or 64-bit floating point values. Some algorithms, such as Binary Array Search, work directly on data structures. More complicated algorithms, especially graph algorithms, rely on a number of fundamental abstract datatypes, which I introduce as needed, such as stacks or priorityqueues. These data types provide fundamental operations that can beefficiently implemented by choosing the right data structure. By the end ofthis book, you will understand how the various algorithms achieve theirperformance. For these algorithms, I will either show full implementationsin Python or refer you to third-party Python packages that provideefficient implementation.

If you review the associated code resources provided with the book, youwill see that for each chapter there is a book.py Python file that can be executed toreproduce all tables within the book. As they say in the business, yourmileage may vary, but the overall trends will still appear.

Figure P-1. Summary of the technical content of the book

At the end of every chapter in the book are challenge exercises that giveyou a chance to put your new knowledge to the test. I encourage you to trythese on your own before you review my sample solutions, found in the coderepository for the book.

About the Code

All the code for this book can be found in the associated GitHub repository,