Guttag - Introduction to Computation and Programming Using Python with Application to Understanding Data

Introduction to Computation and Programming Using Python

with Application to Understanding Data

2016 Massachusetts Institute of Technology

All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.

Printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Names: Guttag, John, author.

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

Description: Second edition. | Cambridge, MA : The MIT Press, [2017] | Includes index.

Identifiers: LCCN 2016019367 | ISBN 9780262529624 (pbk. : alk. paper)

Subjects: LCSH: Python (Computer program language)--Textbooks. | Computer programming--Textbooks.

Classification: LCC QA76.73.P98 G88 2017 | DDC 005.13/3--dc23 LC record available at https://lccn.loc.gov/2016019367

10 9 8 7 6 5 4 3 2 1

To my family:

Olga
David
Andrea
Michael
Mark
Addie

This book is based on courses that have been offered at MIT since 2006, and as Massive Online Open Courses (MOOCs) through edX and MITx since 2012. The first edition of the book was based on a single one-semester course. However, over time I couldnt resist adding more material than could be fit into a semester. The current edition is suitable for a two-semester introductory computer science sequence.

When I started working on the second edition I thought that I would just add a few chapters, but I ended up doing far more. I reorganized the back half of the book, and converted the entire book from Python 2 to Python 3.

The book is aimed at students with little or no prior programming experience who have a desire to understand computational approaches to problem solving. For some of the students the material in this book will be a stepping stone to more advanced computer science courses. But for many of the students it will be their only formal exposure to computer science.

Because this will be the only formal exposure to computer science for many of the students, we emphasize breadth rather than depth. The goal is to provide students with a brief introduction to many topics, so that they will have an idea of whats possible when the time comes to think about how to use computation to accomplish a goal. That said, this is not a computation appreciation book. It is challenging and rigorous. Students who wish to really learn the material will have to spend a lot of time and effort learning to bend the computer to their will.

The main goal of this book is to help students become skillful at making productive use of computational techniques. They should learn to use computational modes of thoughts to frame problems and to guide the process of extracting information from data. The primary knowledge they will take away from this book is the art of computational problem solving.

This book is not easily slotted into a conventional computer science curriculum. They cover the material that we think should become the usual second course in a computer science curriculum (replacing the traditional data structures course).

In , we braid together four strands of material:

• The basics of programming,
• The Python 3 programming language,
• Computational problem solving techniques,
• Computational complexity, and
• Using plots to present information.

We cover most of Pythons features, but the emphasis is on what one can do with a programming language, not on the language itself. For example, by the end of the book has covered only a small fraction of Python, but it has already introduced the notions of exhaustive enumeration, guess-and-check algorithms, bisection search, and efficient approximation algorithms. We introduce features of Python throughout the book. Similarly, we introduce aspects of programming methods throughout the book. The idea is to help students learn Python and how to be a good programmer in the context of using computation to solve interesting problems.

The examples in this book have been tested using Python 3.5. Python 3 cleaned up many of the inconsistencies in the design of the various releases of Python 2 (often referred to as Python 2.x). However, it is not backward compatible. That meant that most programs written using Python 2 cannot be run using implementations of Python 3. For that reason, Python 2.x continues to be widely used. The first time we use features of Python 3 that differ from Python 2, we point out how the same thing could be accomplished in Python 2. All of the examples in this book are available online in both Python 3.5 and Python 2.7.

, but not both, in our one-semester introductory course.

most students than what is typically covered in the second computer science course.

We chose not to include problems at the end of chapters. Instead we inserted finger exercises at opportune points within the chapters. Some are quite short, and are intended to allow readers to confirm that they understood the material they just read. Some are a bit more challenging, and are suitable for exam questions. And others are challenging enough to be useful as homework assignments.

The book has three pervasive themes: systematic problem solving, the power of abstraction, and computation as a way of thinking about the world. When you have finished this book you should have:

• Learned a language, Python, for expressing computations,
• Learned a systematic approach to organizing, writing, and debugging medium-sized programs,
• Developed an informal understanding of computational complexity,
• Developed some insight into the process of moving from an ambiguous problem statement to a computational formulation of a method for solving the problem,
• Learned a useful set of algorithmic and problem reduction techniques,
• Learned how to use randomness and simulations to shed light on problems that dont easily succumb to closed-form solutions, and
• Learned how to use computational tools (including simple statistical, visualization, and machine learning tools) to model and understand data.

Programming is an intrinsically difficult activity. Just as there is no royal road to geometry, there is no royal road to programming. If you really want to learn the material, reading the book will not be enough. At the very least you should try running some of the code in the book. Various versions of the courses from which this book has been derived have been available on MITs Open-CourseWare (OCW) Web site since 2008. The site includes video recordings of lectures and a complete set of problem sets and exams. Since the fall of 2012, edX and MITx have offered online courses that cover much of the material in this book. We strongly recommend that you do the problem sets associated with one of the OCW or edX offerings.

____________

This was Euclids purported response, circa 300 BCE, to King Ptolemys request for an easier way to learn mathematics.

The first edition of this book grew out of a set of lecture notes that I prepared while teaching an undergraduate course at MIT. The course, and therefore this book, benefited from suggestions from faculty colleagues (especially Ana Bell, Eric Grimson, Srinivas Devadas, Fredo Durand, Ron Rivest, and Chris Terman), teaching assistants, and the students who took the course. David Guttag overcame his aversion to computer science, and proofread multiple chapters.