Introduction to Computation and Programming Using Python, Revided & Expanded

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 MITs OpenCourseWare) and was developed for use not only in a conventional classroom but in a massive open online course (or MOOC) offered by the pioneering MIT-Harvard collaboration edX. 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. The book does not require knowledge of mathematics beyond high school algebra, but does assume that readers are comfortable with rigorous thinking and not intimidated by mathematical concepts. 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. Introduction to Computation and Programming Using Python can serve as a stepping-stone to more advanced computer science courses, or as a basic grounding in computational problem solving for students in other disciplines. Contents 8 Preface 14 Acknowledgments 16 1 Getting Started 18 2 Introduction to Python 24 2.1 The Basic Elements of Python 25 2.2 Branching Programs 31 2.3 Strings and Input 33 2.4 Iteration 35 3 Some Simple Numerical Programs 38 3.1 Exhaustive Enumeration 38 3.2 For Loops 40 3.3 Approximate Solutions and Bisection Search 42 3.4 A Few Words About Using Floats 46 3.5 Newton-Raphson 49 4 Functions, Scoping, and Abstraction 51 4.1 Functions and Scoping 52 4.2 Specifications 58 4.3 Recursion 61 4.4 Global Variables 67 4.5 Modules 68 4.6 Files 70 5 Structured Types, Mutability, and Higher-Order Functions 73 5.1 Tuples 73 5.2 Lists and Mutability 75 5.3 Functions as Objects 81 5.4 Strings, Tuples, and Lists 83 5.5 Dictionaries 84 6 Testing and Debugging 87 6.1 Testing 87 6.2 Debugging 93 7 Exceptions and Assertions 101 7.1 Handling Exceptions 101 7.2 Exceptions as a Control Flow Mechanism 104 7.3 Assertions 107 8 Classes and Object-Oriented Programming 108 8.1 Abstract Data Types and Classes 108 8.2 Inheritance 116 8.3 Encapsulation and Information Hiding 120 8.4 Mortgages, an Extended Example 125 9 A Simplistic Introduction to Algorithmic Complexity 130 9.1 Thinking About Computational Complexity 130 9.2 Asymptotic Notation 133 9.3 Some Important Complexity Classes 135 10 Some Simple Algorithms and Data Structures 142 10.1 Search Algorithms 143 10.2 Sorting Algorithms 148 10.3 Hash Tables 154 11 Plotting and More About Classes 158 11.1 Plotting Using PyLab 158 11.2 Plotting Mortgages, an Extended Example 163 12 Stochastic Programs, Probability, and Statistics 169 12.1 Stochastic Programs 170 12.2 Inferential Statistics and Simulation 172 12.3 Distributions 183 12.4 How Often Does the Better Team Win? 191 12.5 Hashing and Collisions 194 13 Random Walks and More About Data Visualization 196 13.1 The Drunkard’s Walk 196 13.2 Biased Random Walks 203 13.3 Treacherous Fields 208 14 Monte Carlo Simulation 210 14.1 Pascal’s Problem 211 14.2 Pass or Don’t Pass? 212 14.3 Using Table Lookup to Improve Performance 216 14.4 Finding π 217 14.5 Some Closing Remarks About Simulation Models 221 15 Understanding Experimental Data 224 15.1 The Behavior of Springs 224 15.2 The Behavior of Projectiles 231 15.3 Fitting Exponentially Distributed Data 235 15.4 When Theory Is Missing 238 16 Lies, Damned Lies, and Statistics 239 16.1 Garbage In Garbage Out (GIGO) 239 16.2 Pictures Can Be Deceiving 240 16.3 Cum Hoc Ergo Propter Hoc 242 16.4 Statistical Measures Don’t Tell the Whole Story 243 16.5 Sampling Bias 245 16.6 Context Matters 246 16.7 Beware of Extrapolation 246 16.8 The Texas Sharpshooter Fallacy 247 16.9 Percentages Can Confuse 249 16.10 Just Beware 250 17 Knapsack and Graph Optimization Problems 251 17.1 Knapsack Problems 251 17.2 Graph Optimization Problems 257 18 Dynamic Programming 269 18.1 Fibonacci Sequences, Revisited 269 18.2 Dynamic Programming and the 0/1 Knapsack Problem 271 18.3 Dynamic Programming and Divide-and-Conquer 278 19 A Quick Look at Machine Learning 279 19.1 Feature Vectors 281 19.2 Distance Metrics 283 19.3 Clustering 287 19.4 Types Example and Cluster 289 19.5 K-means Clustering 291 19.6 A Contrived Example 293 19.7 A Less Contrived Example 297 19.8 Wrapping Up 303 Python 2.7 Quick Reference 304 Index 306 Uploaded by [StormRG] 315 An introductory text that teaches students the art of computational problem solving, covering topics that range from simple algorithms to information visualization.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 (or MOOC) offered by the pioneering MIT-Harvard collaboration edX.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. The book does not require knowledge of mathematics beyond high school algebra, but does assume that readers are comfortable with rigorous thinking and not intimidated by mathematical concepts. 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.Introduction to Computation and Programming Using Python can serve as a stepping-stone to more advanced computer science courses, or as a basic grounding in computational problem solving for students in other disciplines. Getting Started -- Introduction To Python -- Some Simple Numerical Programs -- Functions, Scoping, And Abstraction -- Structured Types, Mutability, And Higher-order Functions -- Testing And Debugging -- Exceptions And Assertions -- Classes And Object-oriented Programming -- A Simplistic Introduction To Algorithmic Complexity -- Some Simple Algorithms And Data Structures -- Plotting And More About Classes -- Stochastic Programs, Probability, And Statistics -- Random Walks And More About Data Visualization -- Monte Carlo Simulation -- Understanding Experimental Data -- Lies, Damned Lies, And Statistics -- Knapsack And Graph Optimization -- Dynamic Programming -- A Quick Look At Machine Learning. John V. Guttag. Includes Bibliographical References And Index.