Includes index.

Preface xiii Acknowledgments xvii 1 Getting Started 1 (6) 2 Introduction To Python 7 (18) 2.1 The Basic Elements of Python 9 (6) 2.1.1 Objects, Expressions, and Numerical Types 9 (3) 2.1.2 Variables and Assignment 12 (2) 2.1.3 Python IDE's 14 (1) 2.2 Branching Programs 15 (3) 2.3 Strings and Input 18 (4) 2.3.1 Input 20 (1) 2.3.2 A Digression About Character Encoding 21 (1) 2.4 Iteration 22 (3) 3 Some Simple Numerical Programs 25 (14) 3.1 Exhaustive Enumeration 25 (2) 3.2 For Loops 27 (3) 3.3 Approximate Solutions and Bisection Search 30 (4) 3.4 A Few Words About Using Floats 34 (3) 3.5 Newton-Raphson 37 (2) 4 Functions, Scoping, And Abstraction 39 (26) 4.1 Functions and Scoping 40 (7) 4.1.1 Function Definitions 40 (2) 4.1.2 Keyword Arguments and Default Values 42 (1) 4.1.3 Scoping 43 (4) 4.2 Specifications 47 (3) 4.3 Recursion 50 (7) 4.3.1 Fibonacci Numbers 52 (2) 4.3.2 Palindromes 54 (3) 4.4 Global Variables 57 (2) 4.5 Modules 59 (2) 4.6 Files 61 (4) 5 Structured Types, Mutability, And Higher-Order Functions 65 (20) 5.1 Tuples 65 (2) 5.1.1 Sequences and Multiple Assignment 67 (1) 5.2 Ranges 67 (1) 5.3 Lists and Mutability 68 (7) 5.3.1 Cloning 73 (1) 5.3.2 List Comprehension 74 (1) 5.4 Functions as Objects 75 (2) 5.5 Strings, Tuples, Ranges, and Lists 77 (2) 5.6 Dictionaries 79 (6) 6 Testing And Debugging 85 (16) 6.1 Testing 86 (6) 6.1.1 Black-Box Testing 87 (1) 6.1.2 Glass-box Testing 88 (2) 6.1.3 Conducting Tests 90 (2) 6.2 Debugging 92 (9) 6.2.1 Learning to Debug 94 (1) 6.2.2 Designing the Experiment 95 (3) 6.2.3 When the Going Gets Tough 98 (1) 6.2.4 When You Have Found "The" Bug 99 (2) 7 Exceptions And Assertions 101 (8) 7.1 Handling Exceptions 101 (4) 7.2 Exceptions as a Control Flow Mechanism 105 (3) 7.3 Assertions 108 (1) 8 Classes And Object-Oriented Programming 109 (26) 8.1 Abstract Data Types and Classes 109 (9) 8.1.1 Designing Programs Using Abstract Data Types 114 (1) 8.1.2 Using Classes to Keep Track of Students and Faculty 115 (3) 8.2 Inheritance 118 (5) 8.2.1 Multiple Levels of Inheritance 121 (2) 8.2.2 The Substitution Principle 123 (1) 8.3 Encapsulation and Information Hiding 123 (7) 8.3.1 Generators 128 (2) 8.4 Mortgages, an Extended Example 130 (5) 9 A Simplistic Introduction To Algorithmic Complexity 135 (16) 9.1 Thinking About Computational Complexity 135 (4) 9.2 Asymptotic Notation 139 (2) 9.3 Some Important Complexity Classes 141 (10) 9.3.1 Constant Complexity 141 (1) 9.3.2 Logarithmic Complexity 141 (1) 9.3.3 Linear Complexity 142 (2) 9.3.4 Log-Linear Complexity 144 (1) 9.3.5 Polynomial Complexity 144 (1) 9.3.6 Exponential Complexity 145 (2) 9.3.7 Comparisons of Complexity Classes 147 (4) 10 Some Simple Algorithms And Data Structures 151 (18) 10.1 Search Algorithms 152 (6) 10.1.1 Linear Search and Using Indirection to Access Elements 153 (1) 10.1.2 Binary Search and Exploiting Assumptions 154 (4) 10.2 Sorting Algorithms 158 (6) 10.2.1 Merge Sort 159 (3) 10.2.2 Exploiting Functions as Parameters 162 (1) 10.2.3 Sorting in Python 162 (2) 10.3 Hash Tables 164 (5) 11 Plotting And More About Classes 169 (14) 11.1 Plotting Using PyLab 169 (6) 11.2 Plotting Mortgages, an Extended Example 175 (8) 12 Knapsack And Graph Optimization Problems 183 (20) 12.1 Knapsack Problems 184 (6) 12.1.1 Greedy Algorithms 184 (4) 12.1.2 An Optimal Solution to the 0/1 Knapsack Problem 188 (2) 12.2 Graph Optimization Problems 190 (13) 12.2.1 Some Classic Graph-Theoretic Problems 195 (1) 12.2.2 Shortest Path: Depth-First Search and Breadth-First Search 196 (7) 13 Dynamic Programming 203 (12) 13.1 Fibonacci Sequences, Revisited 203 (2) 13.2 Dynamic Programming and the 0/1 Knapsack Problem 205 (8) 13.3 Dynamic Programming and Divide-and-Conquer 213 (2) 14 Random Walks And More About Data Visualization 215 (20) 14.1 Random Walks 216 (1) 14.2 The Drunkard's Walk 217 (7) 14.3 Biased Random Walks 224 (7) 14.4 Treacherous Fields 231 (4) 15 Stochastic Programs, Probability, And Distributions 235 (40) 15.1 Stochastic Programs 236 (2) 15.2 Calculating Simple Probabilities 238 (1) 15.3 Inferential Statistics 239 (15) 15.4 Distributions 254 (15) 15.4.1 Probability Distributions 256 (2) 15.4.2 Normal Distributions 258 (5) 15.4.3 Continuous and Discrete Uniform Distributions 263 (1) 15.4.4 Binomial and Multinomial Distributions 264 (1) 15.4.5 Exponential and Geometric Distributions 265 (4) 15.4.6 Benford's Distribution 269 (1) 15.5 Hashing and Collisions 269 (3) 15.6 How Often Does the Better Team Win? 272 (3) 16 Monte Carlo Simulation 275 (16) 16.1 Pascal's Problem 276 (1) 16.2 Pass or Don't Pass? 277 (5) 16.3 Using Table Lookup to Improve Performance 282 (1) 16.4 Finding pi 283 (5) 16.5 Some Closing Remarks About Simulation Models 288 (3) 17 Sampling And Confidence Intervals 291 (14) 17.1 Sampling the Boston Marathon 292 (6) 17.2 The Central Limit Theorem 298 (4) 17.3 Standard Error of the Mean 302 (3) 18 Understanding Experimental Data 305 (22) 18.1 The Behavior of Springs 305 (9) 18.1.1 Using Linear Regression to Find a Fit 309 (5) 18.2 The Behavior of Projectiles 314 (6) 18.2.1 Coefficient of Determination 317 (2) 18.2.2 Using a Computational Model 319 (1) 18.3 Fitting Exponentially Distributed Data 320 (4) 18.4 When Theory Is Missing 324 (3) 19 Randomized Trials And Hypothesis Checking 327 (18) 19.1 Checking Significance 328 (6) 19.2 Beware of P-values 334 (2) 19.3 One-tail and One-sample Tests 336 (2) 19.4 Significant or Not? 338 (2) 19.5 Which N? 340 (2) 19.6 Multiple Hypotheses 342 (3) 20 Conditional Probability And Bayesian Statistics 345 (10) 20.1 Conditional Probabilities 346 (2) 20.2 Bayes' Theorem 348 (2) 20.3 Bayesian Updating 350 (5) 21 Lies, Damned Lies, And Statistics 355 (16) 21.1 Garbage In Garbage Out (GIGO) 355 (1) 21.2 Tests Are Imperfect 356 (1) 21.3 Pictures Can Be Deceiving 357 (2) 21.4 Cum Hoc Ergo Propter Hoc 359 (2) 21.5 Statistical Measures Don't Tell the Whole Story 361 (1) 21.6 Sampling Bias 362 (1) 21.7 Context Matters 363 (1) 21.8 Beware of Extrapolation 364 (1) 21.9 The Texas Sharpshooter Fallacy 364 (3) 21.10 Percentages Can Confuse 367 (1) 21.11 Statistically Significant Differences Can Be Insignificant 368 (1) 21.12 The Regressive Fallacy 369 (1) 21.13 Just Beware 370 (1) 22 A Quick Look At Machine Learning 371 (12) 22.1 Feature Vectors 374 (3) 22.2 Distance Metrics 377 (6) 23 Clustering 383 (20) 23.1 Class Cluster 385 (2) 23.2 K-means Clustering 387 (3) 23.3 A Contrived Example 390 (5) 23.4 A Less Contrived Example 395 (8) 24 Classification Methods 403 (28) 24.1 Evaluating Classifiers 403 (5) 24.2 Predicting the Gender of Runners 408 (1) 24.3 K-nearest Neighbors 408 (7) 24.4 Regression-based Classifiers 415 (10) 24.5 Surviving the Titanic 425 (5) 24.6 Wrapping Up 430 (1) Python 3.5 Quick Reference 431 (4) Index 435

This book introduces students with little or no prior programming experience to theart of computational problem solving using Python and various Python libraries, including PyLab. Itprovides students with skills that will enable them to make productive use of computationaltechniques, including some of the tools and techniques of "data science" for usingcomputation to model and interpret data. The book is based on an MIT course (which became the mostpopular course offered through MIT's OpenCourseWare) and was developed for use not only in aconventional classroom but in in a massive open online course (or MOOC) offered by the pioneeringMIT--Harvard collaboration edX. Students are introduced to Python and the basics of programming inthe context of such computational concepts and techniques as exhaustive enumeration, bisectionsearch, and efficient approximation algorithms. The book does not require knowledge of mathematicsbeyond high school algebra, but does assume that readers are comfortable with rigorous thinking andnot intimidated by mathematical concepts. Although it covers such traditional topics ascomputational complexity and simple algorithms, the book focuses on a wide range of topics not foundin most introductory texts, including information visualization, simulations to model randomness,computational techniques to understand data, and statistical techniques that inform (and misinform)as well as two related but relatively advanced topics: optimization problems and dynamicprogramming. Introduction to Computation and Programming UsingPython can serve as a stepping-stone to more advanced computer science courses, or as abasic grounding in computational problem solving for students in other disciplines.