Dive Into Algorithms A Pythonic Adventure for the Intrepid Beginner (Bradford Tuckfield) (Z-Library)

(This page has no text content)

CONTENTS IN DETAIL COVER TITLEPAGE COPYRIGHT DEDICATION ABOUT THE AUTHOR ABOUT THE TECHNICAL REVIEWER ACKNOWLEDGMENTS INTRODUCTION Who Is This Book For? About This Book Setting Up the Environment Install Python on Windows Install Python on macOS Install Python on Linux

Installing Third-Party Modules Summary CHAPTER 1: PROBLEM-SOLVING WITH ALGORITHMS The Analytic Approach The Galilean Model The Solve-for-x Strategy The Inner Physicist The Algorithmic Approach Thinking with Your Neck Applying Chapman’s Algorithm Solving Problems with Algorithms Summary CHAPTER 2: ALGORITHMS IN HISTORY Russian Peasant Multiplication Doing RPM by Hand Implementing RPM in Python Euclid’s Algorithm Doing Euclid’s Algorithm by Hand Implementing Euclid’s Algorithm in Python Japanese Magic Squares

Creating the Luo Shu Square in Python Implementing Kurushima's Algorithm in Python Summary CHAPTER 3: MAXIMIZING AND MINIMIZING Setting Tax Rates Steps in the Right Direction Turning the Steps into an Algorithm Objections to Gradient Ascent The Problem of Local Extrema Education and Lifetime Income Climbing the Education Hill—the Right Way From Maximization to Minimization Hill Climbing in General When Not to Use an Algorithm Summary CHAPTER 4: SORTING AND SEARCHING Insertion Sort Putting the Insertion in Insertion Sort Sorting via Insertion Measuring Algorithm Efficiency

Why Aim for Efficiency? Measuring Time Precisely Counting Steps Comparing to Well-Known Functions Adding Even More Theoretical Precision Using Big O Notation Merge Sort Merging From Merging to Sorting Sleep Sort From Sorting to Searching Binary Search Applications of Binary Search Summary CHAPTER 5: PURE MATH Continued Fractions Compressing and Communicating Phi More about Continued Fractions An Algorithm for Generating Continued Fractions From Decimals to Continued Fractions From Fractions to Radicals

Square Roots The Babylonian Algorithm Square Roots in Python Random Number Generators The Possibility of Randomness Linear Congruential Generators Judging a PRNG The Diehard Tests for Randomness Linear Feedback Shift Registers Summary CHAPTER 6: ADVANCED OPTIMIZATION Life of a Salesman Setting Up the Problem Brains vs. Brawn The Nearest Neighbor Algorithm Implementing Nearest Neighbor Search Checking for Further Improvements Algorithms for the Avaricious Introducing the Temperature Function Simulated Annealing Tuning Our Algorithm Avoiding Major Setbacks

Allowing Resets Testing Our Performance Summary CHAPTER 7: GEOMETRY The Postmaster Problem Triangles 101 Advanced Graduate-Level Triangle Studies Finding the Circumcenter Increasing Our Plotting Capabilities Delaunay Triangulation Incrementally Generating Delaunay Triangulations Implementing Delaunay Triangulations From Delaunay to Voronoi Summary CHAPTER 8: LANGUAGE Why Language Algorithms Are Hard Space Insertion Defining a Word List and Finding Words Dealing with Compound Words Checking Between Existing Spaces for Potential Words

Using an Imported Corpus to Check for Valid Words Finding First and Second Halves of Potential Words Phrase Completion Tokenizing and Getting N-grams Our Strategy Finding Candidate n + 1-grams Selecting a Phrase Based on Frequency Summary CHAPTER 9: MACHINE LEARNING Decision Trees Building a Decision Tree Downloading Our Dataset Looking at the Data Splitting Our Data Smarter Splitting Choosing Splitting Variables Adding Depth Evaluating Our Decision Tree The Problem of Overfitting Improvements and Refinements Random Forests

Summary CHAPTER 10: ARTIFICIAL INTELLIGENCE La Pipopipette Drawing the Board Representing Games Scoring Games Game Trees and How to Win a Game Building Our Tree Winning a Game Adding Enhancements Summary CHAPTER 11: FORGING AHEAD Doing More with Algorithms Building a Chatbot Text Vectorization Vector Similarity Becoming Better and Faster Algorithms for the Ambitious Solving the Deepest Mysteries INDEX

DIVE INTO ALGORITHMS A Pythonic Adventure for the Intrepid Beginner Bradford Tuckfield San Francisco

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.

About the Author 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/). About the Technical Reviewer 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.

ACKNOWLEDGMENTS “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!

INTRODUCTION 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 delicious—it generates a berry granola parfait, and it’s shown in its entirety in Figure 1. You may be accustomed to calling this type of algorithm a “recipe,” but it fits Donald Knuth’s definition of an algorithm: a finite set of rules that gives a sequence of operations for solving a specific type of problem. Figure 1: 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 Figure 2, which is taken from a form called 1040-EZ. Figure 2: The instructions for filing taxes fit the definition of an algorithm. How is it that taxes and parfaits can have anything in common? Taxes are inevitable, numeric, difficult, and universally disliked. Parfaits are infrequent, artistic, effortless, and adored without exception. The only trait they share is that people prepare both by following algorithms.

In addition to defining algorithm, the great computer scientist Donald Knuth noted that it is nearly synonymous with recipe, procedure, and rigmarole. In the case of filing taxes via the pictured 1040-EZ form, we have 12 steps (a finite list) that specify operations (like addition in step 4 and subtraction in step 6) to solve a specific type of problem: wanting to avoid being imprisoned for tax evasion. In the case of making a parfait, we have six finite steps that specify operations (like placing in step 1 and covering in step 2) to solve a specific type of problem: wanting to have a parfait in your hand or mouth. As you learn more about algorithms, you will begin to see them everywhere and come to appreciate just how powerful they can be. In Chapter 1, we will discuss the remarkable human ability to catch a ball, and find out the details of the algorithm in the human subconscious that enables us to do so. Later, we will talk about algorithms for debugging code, deciding how much to eat at a buffet, maximizing revenue, sorting lists, scheduling tasks, proofreading text, delivering mail, and winning games like chess and sudoku. Along the way, we will learn to judge algorithms according to several attributes that professionals believe are important for them to possess. And we will begin to get a sense of the craftsmanship or even, dare we say, the art of algorithms, which provides scope for creativity and personality in an otherwise precise and quantitative endeavor.

Who Is This Book For? This book provides a friendly introduction to algorithms, with accompanying Python code. To get the greatest possible benefit from it, you should have some experience with the following: 1. Programming/coding. Every major example in the book is illustrated with Python code. We strive to provide walkthroughs and explanations of every code snippet to make the book digestible for someone with no Python experience and not much programming experience. Nevertheless, someone who has at least some basic understanding of the fundamentals of programming—such as variable assignment, for loops, if/then statements, and function calls—will be the most prepared to benefit. 2. High school math. Algorithms are often used to accomplish many of the same goals as math, like solving equations, optimizing, and calculating values. Algorithms also apply many of the same principles that are associated with mathematical thinking, like logic and the need for precise definitions. Some of our discussions veer into mathematical territory, including algebra, the Pythagorean theorem, pi, and the teensiest bit of very basic calculus. We strive to avoid abstruseness and we don’t venture beyond the math taught in American high schools.

Statistics

Uploader

Dive Into Algorithms A Pythonic Adventure for the Intrepid Beginner (Bradford Tuckfield) (Z-Library)

Tags

Text Preview (First 20 pages)

Registered users can read the full content for free

Comments 0

Statistics

Uploader

Dive Into Algorithms A Pythonic Adventure for the Intrepid Beginner (Bradford Tuckfield) (Z-Library)

Tags

Text Preview (First 20 pages)

Registered users can read the full content for free

Comments 0

Reply to Comment

Edit Comment