Introduction to computation and programming using Python : with application to understanding data / John V. Guttag.

Format:

Book

Author/Creator:

Guttag, John V., 1949- author.

Contributor:

Christine Hikawa Fund.

Language:

English

Subjects (All):

Python (Computer program language)--Textbooks.

Python (Computer program language).

Computer programming--Textbooks.

Computer programming.

Genre:

Textbooks.

Physical Description:

xvii, 447 pages ; 23 cm

Edition:

Second edition.

Place of Publication:

Cambridge, Massachusetts : The MIT Press, [2016]

Summary:

This book introduces students with little or no prior programming experience to the art of computational problem solving using Python and various Python libraries, including PyLab. It provides students with skills that will enable them to make productive use of computational techniques, including some of the tools and techniques of data science for using computation to model and interpret data. The book is based on an MIT course (which became the most popular course offered through MIT's OpenCourseWare) and was developed for use not only in a conventional classroom but in a massive open online course (MOOC). This new edition has been updated for Python 3, reorganized to make it easier to use for courses that cover only a subset of the material, and offers additional material including five new chapters. Students are introduced to Python and the basics of programming in the context of such computational concepts and techniques as exhaustive enumeration, bisection search, and efficient approximation algorithms. Although it covers such traditional topics as computational complexity and simple algorithms, the book focuses on a wide range of topics not found in 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 dynamic programming. This edition offers expanded material on statistics and machine learning and new chapters on Frequentist and Bayesian statistics. Book jacket.

Contents:

1 Getting Started 1

2 Introduction to Python 7

2.1 The Basic Elements of Python 9

2.1.1 Objects, Expressions, and Numerical Types 9

2.1.2 Variables and Assignment 12

2.1.3 Python IDE's 14

2.2 Branching Programs 15

2.3 Strings and Input 18

2.3.1 Input 20

2.3.2 A Digression About Character Encoding 21

2.4 Iteration 22

3 Some Simple Numerical Programs 25

3.1 Exhaustive Enumeration 25

3.2 For Loops 27

3.3 Approximate Solutions and Bisection Search 30

3.4 A Few Words About Using Floats 34

3.5 Newton-Raphson 37

4 Functions, Scoping, and Abstraction 39

4.1 Functions and Scoping 40

4.1.1 Function Definitions 40

4.1.2 Keyword Arguments and Default Values 42

4.1.3 Scoping 43

4.2 Specifications 47

4.3 Recursion 50

4.3.1 Fibonacci Numbers 52

4.3.2 Palindromes 54

4.4 Global Variables 57

4.5 Modules 59

4.6 Files 61

5 Structured Types, Mutability, and Higher-Order Functions 65

5.1 Tuples 65

5.1.1 Sequences and Multiple Assignment 67

5.2 Ranges 67

5.3 Lists and Mutability 68

5.3.1 Cloning 73

5.3.2 List Comprehension 74

5.4 Functions as Objects 75

5.5 Strings, Tuples, Ranges, and Lists 77

5.6 Dictionaries 79

6 Testing and Debugging 85

6.1 Testing 86

6.1.1 Black-Box Testing 87

6.1.2 Glass-box Testing 88

6.1.3 Conducting Tests 90

6.2 Debugging 92

6.2.1 Learning to Debug 94

6.2.2 Designing the Experiment 95

6.2.3 When the Going Gets Tough 98

6.2.4 When You Have Found "The" Bug 99

7 Exceptions and Assertions 101

7.1 Handling Exceptions 101

7.2 Exceptions as a Control Flow Mechanism 105

7.3 Assertions 108

8 Classes and Object-Oriented Programming 109

8.1 Abstract Data Types and Classes 109

8.1.1 Designing Programs Using Abstract Data Types 114

8.1.2 Using Classes to Keep Track of Students and Faculty 115

8.2 Inheritance 118

8.2.1 Multiple Levels of Inheritance 121

8.2.2 The Substitution Principle 123

8.3 Encapsulation and Information Hiding 123

8.3.1 Generators 128

8.4 Mortgages, an Extended Example 130

9 A Simplistic Introduction to Whom It May Concern: Algorithmic Complexity 135

9.1 Thinking About Computational Complexity 135

9.2 Asymptotic Notation 139

9.3 Some Important Complexity Classes 141

9.3.1 Constant Complexity 141

9.3.2 Logarithmic Complexity 141

9.3.3 Linear Complexity 142

9.3.4 Log-Linear Complexity 144

9.3.5 Polynomial Complexity 144

9.3.6 Exponential Complexity 145

9.3.7 Comparisons of Complexity Classes 147

10 Some Simple Algorithms and Data Structures 151

10.1 Search Algorithms 152

10.1.1 Linear Search and Using Indirection to Access Elements 153

10.1.2 Binary Search and Exploiting Assumptions 154

10.2 Sorting Algorithms 158

10.2.1 Merge Sort 159

10.2.2 Exploiting Functions as Parameters 162

10.2.3 Sorting in Python 162

10.3 Hash Tables 164

11 Plotting and More about Classes 169

11.1 Plotting Using PyLab 169

11.2 Plotting Mortgages, an Extended Example 175

12 Knapsack and Graph Optimization Problems 183

12.1 Knapsack Problems 184

12.1.1 Greedy Algorithms 184

12.1.2 An Optimal Solution to the 0/1 Knapsack Problem 188

12.2 Graph Optimization Problems 190

12.2.1 Some Classic Graph-Theoretic Problems 195

12.2.2 Shortest Path: Depth-First Search and Breadth-First Search 196

13 Dynamic Programming 203

13.1 Fibonacci Sequences, Revisited 203

13.2 Dynamic Programming and the 0/1 Knapsack Problem 205

13.3 Dynamic Programming and Divide-and-Conquer 213

14 Random Walks and More About Data Visualization 215

14.1 Random Walks 216

14.2 The Drunkards Walk 217

14.3 Biased Random Walks 224

14.4 Treacherous Fields 231

15 Stochastic Programs, Probability, and Distributions 235

15.1 Stochastic Programs 236

15.2 Calculating Simple Probabilities 238

15.3 Inferential Statistics 239

15.4 Distributions 254

15.4.1 Probability Distributions 256

15.4.2 Normal Distributions 258

15.4.3 Continuous and Discrete Uniform Distributions 263

15.4.4 Binomial and Multinomial Distributions 264

15.4.5 Exponential and Geometric Distributions 265

15.4.6 Benford's Distribution 269

15.5 Hashing and Collisions 269

15.6 How Often Does the Better Team Win? 272

16 Monte Carlo Simulation 275

16.1 Pascal's Problem 276

16.2 Pass or Don't Pass? 277

16.3 Using Table Lookup to Improve Performance 282

16.4 Findings π 283

16.5 Some Closing Remarks about Simulation Models 288

17 Sampling and Confidence Intervals 291

17.1 Sampling the Boston Marathon 292

17.2 The Central Limit Theorem 298

17.3 Standard Error of the Mean 302

18 Understanding Experimental Data 305

18.1 The Behavior of Springs 305

18.1.1 Using Linear Regression to Find a Fit 309

18.2 The Behavior of Projectiles 314

18.2.1 Coefficient of Determination 317

18.2.2 Using a Computational Model 319

18.3 Fitting Exponentially Distributed Data 320

18.4 When Theory is Missing 324

19 Randomized Trials and Hypothesis Checking 327

19.1 Checking Significance 328

19.2 Beware of P-values 334

19.3 One-tail and One-sample Tests 336

19.4 Significant or Not? 338

19.5 Which N? 340

19.6 Multiple Hypotheses 342

20 Conditional Probability and Bayesian Statistics 345

20.1 Conditional Probabilities 346

20.2 Bayes' Theorem 348

20.3 Bayesian Updating 350

21 Lies, Damned Lies, and Statistics 355

21.1 Garbage in Garbage Out (GIGO) 355

21.2 Tests Are Imperfect 356

21.3 Pictures Can Be Deceiving 357

21.4 Cum Hoc Ergo Propter Hoc 359

21.5 Statistical Measures Don't Tell the Whole Story 361

21.6 Sampling Bias 362

21.7 Context Matters 363

21.8 Beware of Extrapolation 364

21.9 The Texas Sharpshooter Fallacy 364

21.10 Percentages Can Confuse 367

21.11 Statistically Significant Differences Can Be Insignificant 368

21.12 The Regressive Fallacy 369

21.13 Just Beware 370

22 A Quick Look at Machine Learning 371

22.1 Feature Vectors 374

22.2 Distance Metrics 377

23 Clustering 383

23.1 Class Cluster 385

23.2 K-means Clustering 387

23.3 A Contrived Example 390

23.4 A Less Contrived Example 395

24 Classification Methods 403

24.1 Evaluating Classifiers 403

24.2 Predicting the Gender of Runners 408

24.3 K-nearest Neighbors 408

24.4 Regression-based Classifiers 415

24.5 Surviving the Titanic 425

24.6 Wrapping Up 430.

Notes:

Includes index.

Includes bibliographical references and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Christine Hikawa Fund.

ISBN:

9780262529624

0262529629

OCLC:

949922840