Dive Into Algorithms: A Pythonic Adventure for the Intrepid Beginner
248
Dive Into Algorithms: A Pythonic Adventure for the Intrepid Beginner
248Paperback
-
PICK UP IN STORECheck Availability at Nearby Stores
Available within 2 business hours
Related collections and offers
Overview
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.
Product Details
| ISBN-13: | 9781718500686 |
|---|---|
| Publisher: | No Starch Press |
| Publication date: | 01/25/2021 |
| Pages: | 248 |
| Sales rank: | 658,459 |
| Product dimensions: | 7.00(w) x 9.20(h) x 0.70(d) |
About the Author
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