Introduction to Computation and Programming Using Python, Revised and Expanded Edition

by Guttag

ISBN: 9780262316651 | Copyright 2013


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.

This is the ‘computational thinking’ book we have all been waiting for! With humor and historical anecdotes, John Guttag conveys the breadth and joy of computer science without compromise to technical detail. This book is perfect for any student who wants to explore the essence of computer science.

Jeannette M. Wing President's Professor of Computer Science and Department Head, Carnegie Mellon University

John Guttag is an extraordinary teacher and an extraordinary writer. (Perhaps having been an undergraduate English major—an uncommon stepping stone to the leadership of the world’s top EECS department—has something to do with this.) This is not ‘a Python book’—although you will learn Python. Nor is it a ‘programming book’—although you will learn to program. It is a rigorous but eminently readable introduction to computational problem solving.

Ed Lazowska Bill & Melinda Gates Chair in Computer Science & Engineering, University of Washington

There’s no such thing as the only computer science book you’ll ever need. But if you had to pick only one, this would be a great choice. You’ll begin by getting a solid introduction to programming in Python. Armed with that, you’ll go hands-on with important computing ideas like random methods, statistics, and optimization, using tools of great theoretical beauty and great practical importance.

Hal Abelson coauthor (with Gerald Jay Sussman) of Structure and Interpretation of Computer Programs
Expand/Collapse All
Contents (pg. vii)
Preface (pg. xiii)
Acknowledgments (pg. xv)
1 Getting Started (pg. 1)
2 Introduction to Python (pg. 7)
2.1 The Basic Elements of Python (pg. 8)
2.2 Branching Programs (pg. 14)
2.3 Strings and Input (pg. 16)
2.4 Iteration (pg. 18)
3 Some Simple Numerical Programs (pg. 21)
3.1 Exhaustive Enumeration (pg. 21)
3.2 For Loops (pg. 23)
3.3 Approximate Solutions and Bisection Search (pg. 25)
3.4 A Few Words About Using Floats (pg. 29)
3.5 Newton-Raphson (pg. 32)
4 Functions, Scoping, and Abstraction (pg. 34)
4.1 Functions and Scoping (pg. 35)
4.2 Specifications (pg. 41)
4.3 Recursion (pg. 44)
4.4 Global Variables (pg. 50)
4.5 Modules (pg. 51)
4.6 Files (pg. 53)
5 Structured Types, Mutability, and Higher-Order Functions (pg. 56)
5.1 Tuples (pg. 56)
5.2 Lists and Mutability (pg. 58)
5.3 Functions as Objects (pg. 64)
5.4 Strings, Tuples, and Lists (pg. 66)
5.5 Dictionaries (pg. 67)
6 Testing and Debugging (pg. 70)
6.1 Testing (pg. 70)
6.2 Debugging (pg. 76)
7 Exceptions and Assertions (pg. 84)
7.1 Handling Exceptions (pg. 84)
7.2 Exceptions as a Control Flow Mechanism (pg. 87)
7.3 Assertions (pg. 90)
8 Classes and Object-Oriented Programming (pg. 91)
8.1 Abstract Data Types and Classes (pg. 91)
8.2 Inheritance (pg. 99)
8.3 Encapsulation and Information Hiding (pg. 103)
8.4 Mortgages, an Extended Example (pg. 108)
9 A Simplistic Introduction to Algorithmic Complexity (pg. 113)
9.1 Thinking About Computational Complexity (pg. 113)
9.2 Asymptotic Notation (pg. 116)
9.3 Some Important Complexity Classes (pg. 118)
10 Some Simple Algorithms and Data Structures (pg. 125)
10.1 Search Algorithms (pg. 126)
10.2 Sorting Algorithms (pg. 131)
10.3 Hash Tables (pg. 137)
11 Plotting and More About Classes (pg. 141)
11.1 Plotting Using PyLab (pg. 141)
11.2 Plotting Mortgages, an Extended Example (pg. 146)
12 Stochastic Programs, Probability, and Statistics (pg. 152)
12.1 Stochastic Programs (pg. 153)
12.2 Inferential Statistics and Simulation (pg. 155)
12.3 Distributions (pg. 166)
12.4 How Often Does the Better Team Win? (pg. 174)
12.5 Hashing and Collisions (pg. 177)
13 Random Walks and More About Data Visualization (pg. 179)
13.1 The Drunkard’s Walk (pg. 179)
13.2 Biased Random Walks (pg. 186)
13.3 Treacherous Fields (pg. 191)
14 Monte Carlo Simulation (pg. 193)
14.1 Pascal’s Problem (pg. 194)
14.2 Pass or Don’t Pass? (pg. 195)
14.3 Using Table Lookup to Improve Performance (pg. 199)
14.4 Finding π (pg. 200)
14.5 Some Closing Remarks About Simulation Models (pg. 204)
15 Understanding Experimental Data (pg. 207)
15.1 The Behavior of Springs (pg. 207)
15.2 The Behavior of Projectiles (pg. 214)
15.3 Fitting Exponentially Distributed Data (pg. 218)
15.4 When Theory Is Missing (pg. 221)
16 Lies, Damned Lies, and Statistics (pg. 222)
16.1 Garbage In Garbage Out (GIGO) (pg. 222)
16.2 Pictures Can Be Deceiving (pg. 223)
16.3 Cum Hoc Ergo Propter Hoc (pg. 225)
16.4 Statistical Measures Don’t Tell the Whole Story (pg. 226)
16.5 Sampling Bias (pg. 228)
16.6 Context Matters (pg. 229)
16.7 Beware of Extrapolation (pg. 229)
16.8 The Texas Sharpshooter Fallacy (pg. 230)
16.9 Percentages Can Confuse (pg. 232)
16.10 Just Beware (pg. 233)
17 Knapsack and Graph Optimization Problems (pg. 234)
17.1 Knapsack Problems (pg. 234)
17.2 Graph Optimization Problems (pg. 240)
18 Dynamic Programming (pg. 252)
18.1 Fibonacci Sequences, Revisited (pg. 252)
18.2 Dynamic Programming and the 0/1 Knapsack Problem (pg. 254)
18.3 Dynamic Programming and Divide-and-Conquer (pg. 261)
19 A Quick Look at Machine Learning (pg. 262)
19.1 Feature Vectors (pg. 264)
19.2 Distance Metrics (pg. 266)
19.3 Clustering (pg. 270)
19.4 Types Example and Cluster (pg. 272)
19.5 K-means Clustering (pg. 274)
19.6 A Contrived Example (pg. 276)
19.7 A Less Contrived Example (pg. 280)
19.8 Wrapping Up (pg. 286)
Python 2.7 Quick Reference (pg. 287)
Index (pg. 289)

John V. Guttag

John V. Guttag is the Dugald C. Jackson Professor of Computer Science and Electrical Engineering at MIT.