# Dive Into Algorithms: A Pythonic Adventure for the Intrepid Beginner

248# Dive Into Algorithms: A Pythonic Adventure for the Intrepid Beginner

248## Paperback

## Overview

*Dive Into Algorithms*is a broad introduction to algorithms using the Python Programming Language.*Dive Into Algorithms*is a wide-ranging, Pythonic tour of many of the world's most interesting algorithms. With little more than a bit of computer programming experience and basic high-school math, you'll explore standard computer science algorithms for searching, sorting, and optimization; human-based algorithms that help us determine how to catch a baseball or eat the right amount at a buffet; and advanced algorithms like ones used in machine learning and artificial intelligence. You'll even explore how ancient Egyptians and Russian peasants used algorithms to multiply numbers, how the ancient Greeks used them to find greatest common divisors, and how Japanese scholars in the age of samurai designed algorithms capable of generating magic squares.

You'll explore algorithms that are useful in pure mathematics and learn how mathematical ideas can improve algorithms. You'll learn about an algorithm for generating continued fractions, one for quick calculations of square roots, and another for generating seemingly random sets of numbers.

You'll also learn how to:

Once you've finished this book you'll understand how to code and implement important algorithms as well as how to measure and optimize their performance, all while learning the nitty-gritty details of today's most powerful algorithms.

## Related collections and offers

## Product Details

ISBN-13: | 9781718500686 |
---|---|

Publisher: | No Starch Press |

Publication date: | 01/25/2021 |

Pages: | 248 |

Sales rank: | 327,298 |

Product dimensions: | 7.00(w) x 9.20(h) x 0.70(d) |

## About the Author

**Bradford Tuckfield**, PhD, is the founder of Kmbara, which solves problems using machine learning, AI, chatbots, and other data-based innovations. The author of Applied Unsupervised Learning with R, his work has also been featured in top scholarly journals, and his essays on culture and public policy can be seen in Quillette, National Affairs, and other prestigious outlets.

## Table of Contents

Acknowledgments xiii

Introduction xv

Who Is This Book For? xvii

About This Book xviii

Setting Up the Environment xix

Install Python on Windows xix

Install Python on macOS xx

Install Python on Linux xx

Installing Third-Party Modules xxi

Summary xxi

1 Problem-Solving With Algorithms 1

The Analytic Approach 2

The Galilean Model 2

The Solve-for-x Strategy 4

The Inner Physicist 5

The Algorithmic Approach 6

Thinking with Your Neck 6

Applying Chapman's Algorithm 9

Solving Problems with Algorithms 10

Summary 12

2 Algorithms in History 13

Russian Peasant Multiplication 14

Doing RPM by Hand 14

Implementing RPM in Python 18

Euclid's Algorithm 20

Doing Euclid's Algorithm by Hand 20

Implementing Euclid's Algorithm in Python 21

Japanese Magic Squares 22

Creating the Luo Shu Square in Python 22

Implementing Kurushima's Algorithm in Python 24

Summary 34

3 Maximizing and Minimizing 35

Setting Tax Rates 36

Steps in the Right Direction 36

Turning the Steps into an Algorithm 39

Objections to Gradient Ascent 41

The Problem of Local Extrema 42

Education and Lifetime Income 42

Climbing the Education Hill-the Right Way 44

From Maximization to Minimization 45

Hill Climbing in General 47

When Not to Use an Algorithm 48

Summary 50

4 Sorting and Searching 51

Insertion Sort 52

Putting the Insertion in Insertion Sort 52

Sorting via Insertion 54

Measuring Algorithm Efficiency 55

Why Aim For Efficiency? 56

Measuring Time Precisely 57

Counting Steps 57

Comparing to Well-Known Functions 60

Adding Even More Theoretical Precision 63

Using Big O Notation 64

Merge Sort 65

Merging 66

From Merging to Sorting 68

Sleep Sort 70

From Sorting to Searching 72

Binary Search 73

Applications of Binary Search 75

Summary 76

5 Pure Math 77

Continued Fractions 78

Compressing and Communicating Phi 79

More about Continued Fractions 80

An Algorithm for Generating Continued Fractions 82

From Decimals to Continued Fractions 86

From Fractions to Radicals 88

Square Roots 89

The Babylonian Algorithm 89

Square Roots in Python 90

Random Number Generators 91

The Possibility of Randomness 91

Linear Congruential Generators 92

Judging a PRNG 93

The Diehard Tests for Randomness 95

Linear Feedback Shift Registers 97

Summary 99

7 Advanced Optimization 101

Life of a Salesman 102

Setting Up the Problem 103

Brains vs. Brawn 106

The Nearest Neighbor Algorithm 108

Implementing Nearest Neighbor Search 108

Checking for Further Improvements 110

Algorithms for the Avaricious 112

Introducing the Temperature Function 113

Simulated Annealing 115

Tuning Our Algorithm 118

Avoiding Major Setbacks 120

Allowing Resets 121

Testing Our Performance 122

Summary 124

7 Geometry 125

The Postmaster Problem 126

Triangles 101 128

Advanced Graduate-Level Triangle Studies 130

Finding the Circumcenter 131

Increasing Our Plotting Capabilities 133

Delaunay Triangulation 134

Incrementally Generating Delaunay Triangulations 136

Implementing Delaunay Triangulations 139

From Delaunay to Voronoi 143

Summary 147

8 Language 149

Why Language Algorithms Are Hard 150

Space Insertion 150

Defining a Word List and Finding Words 151

Dealing with Compound Words 152

Checking Between Existing Spaces for Potential Words 153

Using an Imported Corpus to Check for Valid Words 154

Finding First and Second Halves of Potential Words 156

Phrase Completion 159

Tokenizing and Getting N-grams 159

Our Strategy 160

Finding Candidate n + 1-grams 161

Selecting a Phrase Based on Frequency 162

Summary 163

9 Machine Learning 165

Decision Trees 165

Building a Decision Tree 167

Downloading Our Dataset 168

Looking at the Data 168

Splitting Our Data 169

Smarter Splitting 171

Choosing Splitting Variables 173

Adding Depth 175

Evaluating Our Decision Tree 178

The Problem of Overfitting 179

Improvements and Refinements 181

Random Forests 182

Summary 183

10 Artificial Intelligence 185

La Pipopipette 186

Drawing the Board 187

Representing Games 188

Scoring Games 189

Game Trees and How to Win a Game 190

Building Our Tree 192

Winning a Game 195

Adding Enhancements 199

Summary 200

11 Forging Ahead 201

Doing More with Algorithms 202

Building a Chatbot 203

Text Vectorization 204

Vector Similarity 206

Becoming Better and Faster 209

Algorithms for the Ambitious 209

Solving the Deepest Mysteries 212

Index 215