Index

NUMBERS AND SYMBOLS

7×7 magic square, testing code for, 33

% (modulo) operator

Euclid’s algorithm, 21

Kurushima’s algorithm, 2728

RPM (Russian peasant multiplication), 19

rules, 32

[] (square brackets)

using with list comprehension, 152

using with loc functionality, 19

A

acceleration

estimating for thrown ball, 10

observing for thrown ball, 9

AI (artificial intelligence). See also decision trees; game trees; random forests

adding enhancements, 199

drawing the board, 187188

game trees and winning games, 190199

la pipopipette, 186187

representing games, 188189

scoring games, 189190

algebra, 5

algorithmic approach

Chapman’s algorithm, 910

thinking with your neck, 69

algorithms, 13

adding theoretical precision, 6364

alpha–beta pruning, 199

avoiding use of, 4849

Babylonian, 90

Bowyer-Watson, 136

comparing to functions, 6063

counting steps, 5760

divide and conquer, 69

doing more with, 202203

finding maximum, 42

gaining expertise, 209

measuring efficiency, 5557

measuring time, 57

merging sorted lists, 67

minimax, 195198

performing “by hand,” 1418, 2021

perturb search, 112

refraining from using, 4849

solving problems with, 1011

tax rates, 39

using big O notation, 6465

within algorithms, 17

Al-Khwarizmi, 5, 10

alpha–beta pruning algorithm, 199

analytic approach

Galilean model, 24

inner physicist, 56

solve-for-x strategy, 45

angle, tangent of, 89

annealing, process of, 117

antidiagonal of square matrix, 2627

append() method, RPM (Russian peasant multiplication), 18

arguments, magic squares, 3134

artificial intelligence (AI), 185186

adding enhancements, 199

drawing the board, 187188

game trees and winning games, 190199

la pipopipette, 186187

representing games, 188189

scoring games, 189190

asymptote, relationship to maximum, 3940

B

Babylonian algorithm, 90

ball. See also the outfielder problem

horizontal position of, 7

plotting trajectory of, 12, 4, 7

tangent calculation, 89

ball_trajectory() function, 34

baseball, scientific features of, 6

bell curve, 9596

between_spaces variable, creating, 154

big O notation

sleep sort’s runtime, 72

using, 6465

billiard balls and randomness, 91

binary branching process, using with decision trees, 166167

binary expansion, 17

binary search, 7375

bisect, geometric terminology, 130

bits, string of, 9798

board, drawing for dots and boxes game, 187189

bootstrapping, 91

Bowyer-Watson algorithm, 136. See also DT (Delaunay triangulation); triangulation

brain, “wetware” of, 5

branching process, using with decision trees, 166167

brute force solution, using in TSP (traveling salesman problem), 107

Bush, Vannevar, 6

C

calculus, rules of, 38

centroid of triangle, finding, 131133

Chapman, Seville, 6

Chapman’s algorithm, 911. See also the outfielder problem

chatbot, building, 203208

chess, solving eight queens puzzle, 209212

Chesterton, G. K., 151

circles, drawing, 133

circumcenters

finding for triangles, 131133

plotting, 145

relationship to triangles, 134

circumcircles

plotting, 145

relationship to triangles, 132, 134

combinatorial explosion, using in TSP (traveling salesman problem), 108

compound words, dealing with, 152153. See also words

constructive methods of Euclid, 20

continued fractions. See also fractions to radicals

algorithm for generating, 8285

compressing and communicating Phi, 7980

versus decimals, 8688

overview, 78, 8082

to radicals, 88

continued square roots, 88

corpus, 149, 160. See also imported corpus

cosine similarity, 206208

Counter() function, using with n + 1-gram, 161

counting steps, 5760

D

decimals to continued fractions, 8688

decision trees. See also AI (artificial intelligence) game trees; machine learning; random forests

adding depth to, 175177

building, 167

calculating happiness levels, 170

choosing split points, 182

choosing splitting variables, 173175, 182

downloading datasets, 168

evaluating, 178182

looking at data, 168169

nodes, 167

out-of-sample observations, 180

overfitting, 181182

overview, 165166

prediction errors, 171172

problem of overfitting, 179181

pruning, 182, 199

in-sample observations, 180

simplifying, 181182

split points, 171

splitting data, 169173

test sets, 180

training sets, 180

underfitting, 181182

using nested lists with, 176

Delaunay triangulation (DT). See also geometry

generating, 136139

implementing, 139143

overview, 134136

purpose of, 136

returning from points, 142

to Voronoi, 143147

derivative, calculating, 38

Devlin, Keith, 56

dictionary object, creating for chatbot, 203

Diehard tests for randomness, 9597

divide and conquer algorithm, 69

dogs, catching Frisbees, 6

dots and boxes game. See also games

drawing board for, 187188

playing, 186187

scoring, 190

doubling column, RPM (Russian peasant multiplication), 1420

down_left, Kurushima’s algorithm, 2829

drawgame() function, using with games, 188189

drawing circles, 133

drawlattice() function, using with games, 188189

DT (Delaunay triangulation). See also Bowyer-Watson algorithm; triangulation

generating, 136139

implementing, 139143

overview, 134136

purpose of, 136

returning from points, 142

to Voronoi, 143147

E

education and lifetime income, 4245

Elements, 20

equilateral, geometric terminology, 130

ESS (European Social Survey), using with decision trees, 168

Euclid’s algorithm, 2022, 8485

exclusive OR operation, 98

exponential function, 6061

F

False, Kurushima’s algorithm, 27

feedback shift register, 98

file-sorting method, 5254. See also sorted filing cabinets

fillsquare() function, Kurushima’s algorithm, 3132

finding words, 151152

finditer() function, using with words, 152

findnearest() function, using in TSP (traveling salesman problem), 109

float('nan') function, using with Kurushima’s algorithm, 24

floor() function, using for binary search, 7374

for loop, using with words and spaces, 157

fractions to radicals, 88. See also continued fractions

Franklin, Benjamin, 126

Frisbee, trajectory vectors, 6

functions

inverting, 75

recursion, 22

G

Galilean model, 25

game trees. See also AI (artificial intelligence); decision trees; random forests

building, 192195

and winning games, 190192

games. See also dots and boxes game

choosing moves, 195198

minimax algorithm, 195198

representing, 188189

scoring, 189190

winning, 195198

Gaussian normal curve, 96

gen_delaunay() function, passing x and y values to, 143

generate_tree() function, using with games, 194

genlines function, using with triangles, 129

genlines function, TSP (traveling salesman problem), 104

geometry. See also DT (Delaunay triangulation)

postmaster problem, 126128

representing points, 128

tangent of angle, 89

terminology, 130

triangles, 128134

get_number() function, using with continued fractions, 85

get_prediction() function, using with decision trees, 178179

get_split() function, using with decision trees, 174176

get_splitpoint() function, using with decision trees, 174

git bisect software, using for binary search, 75

global variables, defining for simulated annealing, 122

golden ratio, 7879

gradient ascent, 35

climbing income hill, 4445

implementing, 4041

local extrema, 4244

objections, 4142

using, 49

gradient descent, 35, 47

Gravity’s Rainbow, 3

greedy algorithms, TSP (traveling salesman problem), 112113

guided search, using in TSP (traveling salesman problem), 112

H

half_double dataframe, RPM (Russian peasant multiplication), 18

halving column, RPM (Russian peasant multiplication), 1420

happiness levels, calculating with decision trees, 170

hill climbing, 4748

howfull argument, Kurushima’s algorithm, 3132

I

if statement

inserting pop() function into, 6667

using with words and spaces, 151

imported corpus, using to check for valid words, 154155. See also corpus

inner physicist theory, 56

in-sample observations, using with decision trees, 180

insert() function, using with bits, 98

insertion sort, 5255

comparing to exponential function, 61

counting steps in, 6364

step counter, 58

installing, matplotlib module, 3

integers, dividing to get quotient, 84

inverse_sin(0.9) function, using for binary search, 75

inverting functions, 75

irrational number, 79

J

Japanese magic squares. See also magic squares; squares

Kurushima’s algorithm in Python, 2430

Luo Shu square in Python, 2223

K

Kepler, Johannes, 78

k-means machine-learning method, 56

k-NN machine-learning method, 56

Kurushima’s algorithm

function, 3031

rules, 2528

L

la pipopipette, 186187

language algorithms

difficulty, 150

phrase completion, 159163

space insertion, 150158

lattice, using with la pipopipette, 186187

LCGs (linear congruential generators), 9293

left and right variables, Python, 66

Leibniz, Gottfried Wilhelm, 130131

LFSRs (linear feedback shift registers), 9799

lifetime income and education, 4245

lines of sight, plotting for thrown ball, 78

list comprehensions, 149, 156

list indexing syntax, Python, 6869

lists, sorting, 153

loc functionality, RPM (Russian peasant multiplication), 19

local extrema, problem, 4245

loops, RPM (Russian peasant multiplication), 18

lower bound, defining for binary search, 73

lower() method, using with chatbot, 203

Lucas, Édouard, 186

Luo Shu square, creating in Python, 2223

M

machine learning. See also decision trees

overview, 165

random forests, 182183

machine-learning methods, k-means clustering and k-NN, 56

magic eye, 147

magic squares, 2223. See also Japanese magic squares; squares

arguments, 3134

Kurushima’s algorithm, 3031

of odd dimension, 24

patterns, 34

“walk” through, 28

The Math Instinct: Why You’re a Mathematical Genius (Along with Lobsters, Birds, Cats, and Dogs), 56

math library, Python, 7374

mathematical physics, interpretation of, 92

math.floor(), RPM (Russian peasant multiplication), 18

matplotlib module

setting tax rates, 3637

using with dots and boxes game, 187188

matplotlib module, installing, 3

max() function, using with numpy, 162

maxima and minima, 35

maximization and minimization, 4548

maximum

and asymptote approach, 3940

education and lifetime income, 4445

and minimum of step values, 6061

revenue, 39

solving first-order conditions, 42

taxation/revenue curve, 4142

maxitin argument, adding, 122

merging to sorting, 65, 6870. See also sorting

Mersenne Twister PRNG, 99

metaheuristics, metaphor based, 117118

Mikami, Yoshio, 22

Millennium Prize Problems, 212

minimax algorithm

using to make decisions, 199

using to win games, 195198

minimax() function, calling, 198

modulo (%) operator

Euclid’s algorithm, 21

Kurushima’s algorithm, 2728

RPM (Russian peasant multiplication), 19

rules, 32

Monte Carlo methods, 199

mystery number and continued fraction, 81

N

n + 1-grams, finding, 161163

n queens completion problem, solving for chess, 210211

nan entries, filling in, 2528, 3031

Navier-Stokes equations, 5

nearest neighbor algorithm, TSP (traveling salesman problem), 108110

nested lists, using with decision trees, 176

nested radicals, 88

next_random() function, 93

n-gram, tokenizing and getting, 159160

Norvig, Peter, 160

NP (nondeterministic polynomial) complexity class, 212213

numbered file, inserting, 54

numpy module

importing, 60

using to select phrases, 162

using with decision trees, 180181

O

optimization, 101102. See also simulated annealing; TSP (traveling salesman problem)

the outfielder problem, 12, 69. See also ball; Chapman’s algorithm

out-of-sample observations, using with decision trees, 180

overfitting decision trees, 181182

overlapping sums test, 9596

P

P complexity class of problems, 212213

pandas module, using in Python, 19

percentile, using with decision trees, 172173

perpendicular, geometric terminology, 130

perturb() function

modifying, 116

showing end of, 121

updating, 119

using for simulated annealing, 123

using in TSP (traveling salesman problem), 111112

perturb search algorithm, 112. See also simulated annealing

phi

compressing and communicating, 7980

and golden ratio, 78

phrase completion, 159163

plot() function, using with dots and boxes game, 187188

plot_triangle() function

defining, 129

improving, 133134

plotitinerary() function, using in TSP (traveling salesman problem), 105

plotting capabilities, Galilean model, 3

.png file, saving to, 129130

points, representing, 128130

points_to_triangle() function

defining, 128

using in triangulation, 134

polynomial, Galilean model, 3

polynomial time, verifying solutions in, 212

pop() method

inserting into if statements, 6667

using with bits, 98

pop() method, sorting via insertion, 55

postmaster problem, 126128

potential words. See also words

checking for, 153154

finding halves of, 156158

prediction errors, decision trees, 171172

print(cities) function, TSP (traveling salesman problem), 103

print(lines) function, TSP (traveling salesman problem), 104

print(square) function, using with Kurushima’s algorithm, 2425

PRNGs (pseudorandom number generators), 9299

problems, solving with algorithms, 1011

Project Gutenberg, 160

pruning decision trees, 182, 199

pseudorandomness, 9293

Pynchon, Thomas, 3

Pythagorean theorem

using, 105

using with triangles, 130

using in TSP (traveling salesman problem), 108109

Python

creating Luo Shu square, 2223

Euclid’s algorithm, 2022

feedback shift register, 98

Galilean model, 3

implementing RPM (Russian peasant multiplication), 1820

Kurushima’s algorithm, 24

left and right variables, 66

list indexing syntax, 68

math library, 7374

ordered pairs in, 152

overlapping sums test, 9596

pandas module, 19

random module, 5859

random.choice() function, 28

rules for Kurushima’s algorithm, 2728, 3031

square roots in, 9091

timeit module, 57

using tuples with words and spaces, 152

Q

quotient, getting by dividing integers, 84

R

radicals and fractions, 88

radius, returning for triangle, 132133

Ramanujan, Srinivasa, 88

random forests, 182183. See also decision trees; game trees

random model, Python, 5859

random number generators

judging PRNGs (pseudorandom number generators), 9395

LCDs (linear congruential generators), 9293

LFSRs (linear feedback shift registers), 9799

overview, 91

random.choice() function, Python, 28

randomness

Diehard tests for, 9597

possibility of, 9192

random.seed() function, 59

recursion

of functions, 22

implementing merge sort with, 69

using with Euclid’s algorithm, 85

re.finditer() function, using with words, 152

reindex() method, using with decision trees, 181

remove() function, using with words and spaces, 155

replace() function, using with words and spaces, 155

resetthresh variable, adding, 122

revenue

maximum, 39

showing for tax rates, 3637

right and left variables, Python, 66

RPM (Russian peasant multiplication), 1320

rules, applying with Kurushima’s algorithm, 27, 3031

S

science, laws of, 130131

scoring games, 189190

search suggestions, strategy for generating, 160, 162163

searching versus sorting, 7275

Shakespeare’s works, accessing, 160161, 163

siman() function, using for simulated annealing, 122123

Simmons, Joseph, 179

simulated annealing, 115124. See also optimization; perturb search; TSP (traveling salesman problem)

sleep sort, 7072. See also sorting

Smith, David Eugene, 22

solve-for-x strategy, 45, 1011

sorted filing cabinets, merging, 62, 6465. See also file-sorting method

sorting. See also merging to sorting; sleep sort

lists, 153

via insertion, 5455

to searching, 7275

space insertion

checking for potential words, 153154

checking for valid words, 154156

dealing with compound words, 152153

defining word lists, 151152

finding halves of potential words, 156158

finding words, 151152

overview, 150151

spaces

getting substrings between, 153154

inserting into texts, 158

words ending with, 156

split points, choosing for decision trees, 171, 182

splitting variables, choosing for decision trees, 182

square brackets ([])

using with list comprehension, 152

using with loc functionality, 19

square matrix, antidiagonal of, 2627

square roots, 8991

squares, filling in, 3034. See also Japanese magic squares; magic squares

start() function, using with words, 153

statistical methods, bootstrapping as, 91

steps

counting in insertion sort, 5760, 6364

exponential growth, 6061

stochastic gradient ascent, 45

strings, splitting into words, 159160

substrings, getting between spaces, 153154

sudoku puzzles, solving, 211212

T

tangent of angle, 89

tax rates, setting, 3641

taxation/revenue curve, gradient ascent, 41

tax/revenue curve, flipping, 4647

temperature function, TSP (traveling salesman problem), 113115

test sets, using with decision trees, 180

text normalization, using with chatbot, 203

text vectorization, 204206

TFIDF (term frequency-inverse document frequency) method, 204205, 207208

theta, applying to thrown ball, 89

thinking with your neck, 69

time, measuring precisely, 57

timeit module, Python, 57

Titanic lifeboat example, using sleep sort with, 7172

tokenization, performing with chatbot, 204

tokenizing n-grams, 159160

training sets, using with decision trees, 180

translate() method, using with chatbot, 203204

triage and decision trees, 166

triangles

centroid, 131133

creating for postmaster problem, 128134

finding circumcenter of, 131133

plotting, 129, 145146

replacing, 140143

triangulation. See also Bowyer-Watson algorithm; DT (Delaunay triangulation)

defined, 134

of seven points, 135

True, Kurushima’s algorithm, 27

TSP (traveling salesman problem). See also optimization; simulated annealing

greedy algorithms, 112113

improving, 110112

nearest neighbor algorithm, 108110

overview, 102103

versus postmaster problem, 127

setting up, 103108

temperature function, 113115

tuples, using with words and spaces, 152

U

underfitting decision trees, 181182

up_right, Kurushima’s algorithm, 2829

upper bound, defining for binary search, 73

V

vector similarity, determining, 206208

vertex, geometric terminology, 130

Voronoi diagram

generating, 143147

for postmaster problem, 128

W

while loop, Kurushima’s algorithm, 31

while loop

using for binary search, 74

using with bits, 99

using with continued fractions, 85

using with merge sort, 67

using with square roots, 9091

while loop, RPM (Russian peasant multiplication), 18

winning games, 195198

word list, defining, 151152

words. See also compound words; potential words

checking validity with imported corpus, 154156

ending with spaces, 156

finding, 151152

tokenizing, 159160

X

XOR operation, 98

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
54.166.170.195