3E_TOC.pdf

CONTENTS PREFACE............................................................................................................ xv ACKNOWLEDGMENTS................................................................................... xix 1 GETTING STARTE...

CONTENTS PREFACE............................................................................................................ xv ACKNOWLEDGMENTS................................................................................... xix 1 GETTING STARTED...................................................................................... 1 1.1 Terms Introduced in Chapter.......................................................................... 9 2 INTRODUCTION TO PYTHON................................................................. 11 2.1 Installing Python and Python IDEs.............................................................. 13 2.2 The Basic Elements of Python....................................................................... 15 2.2.1 Objects, Expressions, and Numerical Types......................................... 16 2.2.2 Variables and Assignment....................................................................... 19 2.3 Branching Programs....................................................................................... 21 2.4 Strings and Input............................................................................................. 27 2.4.1 Input........................................................................................................... 31 2.4.2 A Digression about Character Encoding.............................................. 32 2.5 While Loops..................................................................................................... 33 2.6 For Loops and Range...................................................................................... 37 2.7 Style Matters..................................................................................................... 41 2.8 Terms Introduced in Chapter........................................................................ 42 3 SOME SIMPLE NUMERICAL PROGRAMS............................................... 45 3.1 Exhaustive Enumeration................................................................................ 45 3.2 Approximate Solutions and Bisection Search.............................................. 50 3.3 A Few Words about Using Floats.................................................................. 56 3.4 Newton–Raphson............................................................................................ 60 3.5 Terms Introduced in Chapter........................................................................ 62 viii INTRODUCTION TO COMPUTATION AND PROGRAMMING USING PYTHON 4 FUNCTIONS, SCOPING, AND ABSTRACTION....................................... 63 4.1 Functions and Scoping................................................................................... 66 4.1.1 Function Definitions................................................................................ 66 4.1.2 Keyword Arguments and Default Values.............................................. 70 4.1.3 Variable Number of Arguments............................................................. 72 4.1.4 Scoping...................................................................................................... 73 4.2 Specifications................................................................................................... 78 4.3 Using Functions to Modularize Code........................................................... 82 4.4 Functions as Objects....................................................................................... 84 4.5 Methods, Oversimplified................................................................................ 86 4.6 Terms Introduced in Chapter........................................................................ 87 5 STRUCTURED TYPES AND MUTABILITY.............................................. 89 5.1 Tuples................................................................................................................ 89 5.1.1 Multiple Assignment................................................................................ 91 5.2 Ranges and Iterables........................................................................................ 92 5.3 Lists and Mutability......................................................................................... 93 5.3.1 Cloning.................................................................................................... 100 5.3.2 List Comprehension............................................................................... 103 5.4 Higher-Order Operations on Lists.............................................................. 105 5.5 Strings, Tuples, Ranges, and Lists................................................................ 107 5.6 Sets................................................................................................................... 110 5.7 Dictionaries.................................................................................................... 112 5.8 Dictionary Comprehension......................................................................... 118 5.9 Terms Introduced in Chapter...................................................................... 121 6 RECURSION AND GLOBAL VARIABLES................................................ 123 6.1 Fibonacci Numbers....................................................................................... 125 6.2 Palindromes................................................................................................... 128 6.3 Global Variables............................................................................................. 132 6.4 Terms Introduced in Chapter...................................................................... 134 CONTENTS ix 7 MODULES AND FILES............................................................................... 135 7.1 Modules.......................................................................................................... 135 7.2 Using Predefined Packages.......................................................................... 138 7.3 Files.................................................................................................................. 142 7.4 Terms Introduced in Chapter...................................................................... 145 8 TESTING AND DEBUGGING................................................................... 147 8.1 Testing............................................................................................................. 148 8.1.1 Black-Box Testing................................................................................... 149 8.1.2 Glass-Box Testing................................................................................... 152 8.1.3 Conducting Tests.................................................................................... 154 8.2 Debugging...................................................................................................... 156 8.2.1 Learning to Debug................................................................................. 159 8.2.2 Designing the Experiment.................................................................... 160 8.2.3 When the Going Gets Tough................................................................ 164 8.2.4 When You Have Found “The” Bug...................................................... 165 8.3 Terms Introduced in Chapter...................................................................... 166 9 EXCEPTIONS AND ASSERTIONS............................................................ 167 9.1 Handling Exceptions..................................................................................... 168 9.2 Exceptions as a Control Flow Mechanism................................................. 174 9.3 Assertions....................................................................................................... 176 9.4 Terms Introduced in Chapter...................................................................... 176 10 CLASSES AND OBJECT-ORIENTED PROGRAMMING........................ 177 10.1 Abstract Data Types and Classes................................................................. 178 10.1.1 Magic Methods and Hashable Types................................................... 184 10.1.2 Designing Programs Using Abstract Data Types...............................186 10.1.3 Using Classes to Keep Track of Students and Faculty.......................187 10.2 Inheritance..................................................................................................... 190 10.2.1 Multiple Levels of Inheritance.............................................................. 194 10.2.2 The Substitution Principle.................................................................... 196 x INTRODUCTION TO COMPUTATION AND PROGRAMMING USING PYTHON 10.3 Encapsulation and Information Hiding..................................................... 197 10.3.1 Generators............................................................................................... 203 10.4 An Extended Example.................................................................................. 206 10.5 Terms Introduced in Chapter...................................................................... 212 11 A SIMPLISTIC INTRODUCTION TO ALGORITHMIC COMPLEXITY.. 213 11.1 Thinking about Computational Complexity.............................................214 11.2 Asymptotic Notation..................................................................................... 218 11.3 Some Important Complexity Classes.......................................................... 221 11.3.1 Constant Complexity............................................................................. 221 11.3.2 Logarithmic Complexity....................................................................... 221 11.3.3 Linear Complexity.................................................................................. 223 11.3.4 Log-Linear Complexity......................................................................... 224 11.3.5 Polynomial Complexity......................................................................... 224 11.3.6 Exponential Complexity........................................................................ 226 11.3.7 Comparisons of Complexity Classes................................................... 228 11.4 Terms Introduced in Chapter...................................................................... 231 12 SOME SIMPLE ALGORITHMS AND DATA STRUCTURES................... 233 12.1 Search Algorithms......................................................................................... 234 12.1.1 Linear Search and Using Indirection to Access Elements................235 12.1.2 Binary Search and Exploiting Assumptions.......................................237 12.2 Sorting Algorithms........................................................................................ 241 12.2.1 Merge Sort............................................................................................... 243 12.2.2 Sorting in Python................................................................................... 247 12.3 Hash Tables..................................................................................................... 250 12.4 Terms Introduced in Chapter...................................................................... 255 13 PLOTTING AND MORE ABOUT CLASSES............................................ 257 13.1 Plotting Using Matplotlib............................................................................. 257 13.2 Plotting Mortgages, an Extended Example................................................263 13.3 An Interactive Plot for an Infectious Disease............................................271 13.4 Terms Introduced in Chapter...................................................................... 279 CONTENTS xi 14 KNAPSACK AND GRAPH OPTIMIZATION PROBLEMS..................... 281 14.1 Knapsack Problems....................................................................................... 282 14.1.1 Greedy Algorithms................................................................................. 283 14.1.2 An Optimal Solution to the 0/1 Knapsack Problem..........................287 14.2 Graph Optimization Problems.................................................................... 291 14.2.1 Some Classic Graph-Theoretic Problems...........................................297 14.2.2 Shortest Path: Depth-First Search and Breadth-First Search...........297 14.3 Terms Introduced in Chapter...................................................................... 304 15 DYNAMIC PROGRAMMING.................................................................... 305 15.1 Fibonacci Sequences, Revisited................................................................... 306 15.2 Dynamic Programming and the 0/1 Knapsack Problem.........................309 15.3 Dynamic Programming and Divide-and-Conquer..................................319 15.4 Terms Introduced in Chapter...................................................................... 320 16 RANDOM WALKS AND MORE ABOUT DATA VISUALIZATION....... 321 16.1 Random Walks............................................................................................... 322 16.2 The Drunkard’s Walk................................................................................... 323 16.3 Biased Random Walks.................................................................................. 331 16.4 Treacherous Fields......................................................................................... 338 16.5 Terms Introduced in Chapter...................................................................... 340 17 STOCHASTIC PROGRAMS, PROBABILITY, AND DISTRIBUTIONS.. 341 17.1 Stochastic Programs...................................................................................... 342 17.2 Calculating Simple Probabilities................................................................. 344 17.3 Inferential Statistics....................................................................................... 346 17.4 Distributions.................................................................................................. 366 17.4.1 Probability Distributions....................................................................... 369 17.4.2 Normal Distributions............................................................................ 371 17.4.3 Continuous and Discrete Uniform Distributions..............................378 17.4.4 Binomial and Multinomial Distributions...........................................379 17.4.5 Exponential and Geometric Distributions.........................................381 17.4.6 Benford’s Distribution........................................................................... 385 xii INTRODUCTION TO COMPUTATION AND PROGRAMMING USING PYTHON 17.5 Hashing and Collisions................................................................................. 386 17.6 How Often Does the Better Team Win?..................................................... 389 17.7 Terms Introduced in Chapter...................................................................... 391 18 MONTE CARLO SIMULATION................................................................ 393 18.1 Pascal’s Problem............................................................................................ 394 18.2 Pass or Don’t Pass?........................................................................................ 396 18.3 Using Table Lookup to Improve Performance..........................................401 18.4 Finding π........................................................................................................ 403 18.5 Some Closing Remarks about Simulation Models....................................409 18.6 Terms Introduced in Chapter...................................................................... 411 19 SAMPLING AND CONFIDENCE.............................................................. 413 19.1 Sampling the Boston Marathon................................................................... 414 19.2 The Central Limit Theorem......................................................................... 422 19.3 Standard Error of the Mean......................................................................... 427 19.4 Terms Introduced in Chapter...................................................................... 430 20 UNDERSTANDING EXPERIMENTAL DATA.......................................... 431 20.1 The Behavior of Springs............................................................................... 431 20.1.1 Using Linear Regression to Find a Fit................................................. 435 20.2 The Behavior of Projectiles.......................................................................... 443 20.2.1 Coefficient of Determination............................................................... 445 20.2.2 Using a Computational Model............................................................. 447 20.3 Fitting Exponentially Distributed Data...................................................... 449 20.4 When Theory Is Missing.............................................................................. 454 20.5 Terms Introduced in Chapter...................................................................... 455 21 RANDOMIZED TRIALS AND HYPOTHESIS CHECKING.................... 457 21.1 Checking Significance................................................................................... 458 21.2 Beware of P-values........................................................................................ 466 21.3 One-tail and One-sample Tests................................................................... 469 21.4 Significant or Not?......................................................................................... 471 21.5 Which N?........................................................................................................ 474 CONTENTS xiii 21.6 Multiple Hypotheses..................................................................................... 476 21.7 Conditional Probability and Bayesian Statistics.......................................479 21.7.1 Conditional Probabilities...................................................................... 481 21.7.2 Bayes’ Theorem...................................................................................... 483 21.8 Terms Introduced in Chapter...................................................................... 486 22 LIES, DAMNED LIES, AND STATISTICS................................................. 487 22.1 Garbage In Garbage Out (GIGO)............................................................... 488 22.2 Tests Are Imperfect....................................................................................... 489 22.3 Pictures Can Be Deceiving........................................................................... 490 22.4 Cum Hoc Ergo Propter Hoc........................................................................ 494 22.5 Statistical Measures Don’t Tell the Whole Story.......................................497 22.6 Sampling Bias................................................................................................. 499 22.7 Context Matters............................................................................................. 500 22.8 Comparing Apples to Oranges.................................................................... 501 22.9 Picking Cherries............................................................................................ 502 22.10 Beware of Extrapolation............................................................................... 502 22.11 The Texas Sharpshooter Fallacy.................................................................. 503 22.12 Percentages Can Confuse............................................................................. 507 22.13 The Regressive Fallacy.................................................................................. 508 22.14 Statistically Significant Differences Can Be Insignificant........................509 22.15 Just Beware..................................................................................................... 510 22.16 Terms Introduced in Chapter...................................................................... 510 23 EXPLORING DATA WITH PANDAS........................................................ 511 23.1 DataFrames and CSV Files........................................................................... 511 23.2 Creating Series and DataFrames................................................................. 514 23.3 Selecting Columns and Rows....................................................................... 518 23.3.1 Selection Using loc and iloc.................................................................. 520 23.3.2 Selection by Group................................................................................. 524 23.3.3 Selection by Content.............................................................................. 525 23.4 Manipulating the Data in a DataFrame...................................................... 527 23.5 An Extended Example.................................................................................. 530 xiv INTRODUCTION TO COMPUTATION AND PROGRAMMING USING PYTHON 23.5.1 Temperature Data................................................................................... 530 23.5.2 Fossil Fuel Consumption....................................................................... 541 23.6 Terms Introduced in Chapter...................................................................... 544 24 A QUICK LOOK AT MACHINE LEARNING........................................... 545 24.1 Feature Vectors.............................................................................................. 549 24.2 Distance Metrics............................................................................................ 552 24.3 Terms Introduced in Chapter...................................................................... 559 25 CLUSTERING.............................................................................................. 561 25.1 Class Cluster................................................................................................... 563 25.2 K-means Clustering...................................................................................... 566 25.3 A Contrived Example................................................................................... 569 25.4 A Less Contrived Example........................................................................... 576 25.5 Terms Introduced in Chapter...................................................................... 583 26 CLASSIFICATION METHODS.................................................................. 585 26.1 Evaluating Classifiers.................................................................................... 586 26.2 Predicting the Gender of Runners.............................................................. 591 26.3 K-nearest Neighbors..................................................................................... 593 26.4 Regression-based Classifiers........................................................................ 599 26.5 Surviving the Titanic..................................................................................... 612 26.6 Wrapping Up.................................................................................................. 618 26.7 Terms Introduced in Chapter...................................................................... 618 PYTHON 3.8 QUICK REFERENCE................................................................ 619 INDEX............................................................................................................... 623