Bradford Tuckfield - Dive Into Algorithms

Dive Into Algorithms.Copyright 2021 by Bradford Tuckfield

All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher.

ISBN-13: 978-1-71850-068-6 (print)
ISBN-13: 978-1-71850-069-3 (ebook)

Publisher: William Pollock
Execuitve Editor: Barbara Yien
Production Editors: Maureen Forys, Happenstance Type-O-Rama and Laurel Chun
Developmental Editor: Alex Freed
Cover Design: Gina Redman
Interior Design: Octopod Studios
Technical Reviewer: Alok Malik
Copyeditor: Scout Festa
Compositor: Jeff Lytle, Happenstance Type-O-Rama
Proofreader: Rachel Monaghan
Illustrator: Jeff Wilson, Happenstance Type-O-Rama
Indexer: Valerie Perry

For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly:
No Starch Press, Inc.
245 8th Street, San Francisco, CA 94103
www.nostarch.com

Library of Congress Cataloging-in-Publication Data

Names: Tuckfield, Bradford, author.
Title: Dive into algorithms / Bradford Tuckfield.
Description: San Francisco : No Starch Press, [2020] | Includes index.
Identifiers: LCCN 2020026327 (print) | LCCN 2020026328 (ebook) | ISBN
9781718500686 (paperback) | ISBN 1718500688 (paperback) | ISBN
9781718500693 (ebook)
Subjects: LCSH: Computer algorithms. | Computer programming.
Classification: LCC QA76.9.A43 T83 2020 (print) | LCC QA76.9.A43 (ebook)
| DDC 005.13--dc23
LC record available at https://lccn.loc.gov/2020026327
LC ebook record available at https://lccn.loc.gov/2020026328

No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.

The information in this book is distributed on an As Is basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

Dedicated to my parents, David and Becky Tuckfield, for believing in me and for teaching me la pipopipette.

Bradford Tuckfield is a data scientist and writer. He runs a data science consulting firm called Kmbara (https://kmbara.com/) and a fiction website called Dreamtigers (http://thedreamtigers.com/).

Alok Malik is a data scientist based in New Delhi, India. He works on developing deep learning models in both natural language processing and computer vision with Python. He has developed and deployed solutions such as language models, image and text classifiers, language translators, speech-to-text models, named entity recognizers, and object detectors. He has also co-authored a book on machine learning. In his free time he likes to read about finance, do MOOCs, and play video games on his console.

A word is not the same with one writer as it is with another. One tears it from his guts. The other pulls it out of his overcoat pocket. This is how Charles Peguy described writing individual words. The same thing is true of chapters and whole books. At times, it felt like I was pulling this book out of my overcoat pocket. At other times, it felt like I was tearing it from my guts. It seems appropriate to acknowledge everyone who contributed to the long process, either by loaning me an overcoat or by helping me clean up my spilled guts.

Many kind people helped me on the long path I took to gain the experience and skills required to write this book. My parents, David and Becky Tuckfield, gave me so many gifts, starting with life and education, and continued to believe in me, encourage me, and help me in many other ways too numerous to list here. Scott Robertson gave me my first job writing code, even though I was unqualified and not very good. Randy Jenson gave me my first data science job, again despite my inexperience and limitations. Kumar Kashyap gave me my first chance to lead a development team to implement algorithms. David Zou was the first person to pay me for writing an article ($10 minus PayPal fees for 10 short movie reviews), and that felt so good, it put me on a path to writing more. Aditya Date was the first person to suggest that I write a book and gave me my first chance to do so.

I also received encouragement from many teachers and mentors. David Cardon gave me my first chance to collaborate on academic research, and taught me many things during that process. Bryan Skelton and Leonard Woo showed me examples of what I wanted to grow up to be. Wes Hutchinson taught me crucial algorithms, like k-means clustering, and helped me better understand how algorithms work. Chad Emmett taught me how to think about history and culture, and Chapter 2 is dedicated to him. Uri Simonsohn showed me how to think about data.

Some people helped to make the process of writing this book a joy. Seshu Edala helped me adjust my work schedule to be able to write, and provided constant encouragement. Alex Freed was a joy to work with during the editing process. Jennifer Eagar, via Venmo transfer months before initial publication, unofficially became the first person to buy a copy of the book; that was appreciated during a difficult time. Hlaing Hlaing Tun was supportive, helpful, sweet, and encouraging at every step.

I cannot repay all of these debts of gratitude, but at least I can say thank you. Thank you!

Algorithms are everywhere. You have probably executed a few already today. In this book, you will read about dozens of algorithms: some simple, some complex, some famous, some unknown, all interesting, and all worth learning. The first algorithm of the book is also the most deliciousit generates a berry granola parfait, and its shown in its entirety in . You may be accustomed to calling this type of algorithm a recipe, but it fits Donald Knuths definition of an algorithm: a finite set of rules that gives a sequence of operations for solving a specific type of problem.

An algorithm: a finite set of rules that gives a sequence of operations for solving a specific type of problem

Parfait-making is not the only domain of life governed by algorithms. Every year, the US government requires each adult citizen to execute an algorithm, and strives to imprison those who fail to do so correctly. In 2017, millions of Americans fulfilled this duty by completing the algorithm shown in , which is taken from a form called 1040-EZ.

The instructions for filing taxes fit the definition of an algorithm.