John V. Guttag - Introduction to Computation and Programming Using Python: With Application to Computational Modeling and Understanding Data

2021 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.

This book was set in Minion Pro by New Best-set Typesetters Ltd.

Library of Congress Cataloging-in-Publication Data

Names: Guttag, John, author.

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

Description: Third edition. | Cambridge, Massachusetts : The MIT Press, [2021] | Includes index.

Identifiers: LCCN 2020036760 | ISBN 9780262542364 (paperback)

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

Classification: LCC QA76.73.P98 G88 2021 | DDC 005.13/3dc23

LC record available at https://lccn.loc.gov/2020036760

10987654321

d_r0

To my family:

Olga

David

Andrea

Michael

Mark

Addie

Pierce

1. Chapter 1
2. Chapter 2
3. Chapter 3
4. Chapter 4
5. Chapter 5
6. Chapter 6
7. Chapter 7
8. Chapter 8
9. Chapter 9
10. Chapter 10
11. Chapter 11
12. Chapter 12
13. Chapter 13
14. Chapter 14
15. Chapter 15
16. Chapter 16
17. Chapter 17
18. Chapter 18
19. Chapter 19
20. Chapter 20
21. Chapter 21
22. Chapter 22
23. Chapter 23
24. Chapter 24
25. Chapter 25
26. Chapter 26

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 couldn't resist adding more material than could be fit into a semester. The current edition is suitable for either a two-semester or a three-quarter introductory computer science sequence.

The book is aimed at 1) readers with little or no prior programming experience who have a desire to understand computational approaches to problem solving, and 2) more experienced programmers who want to learn how to use computation to model things or explore data.

We emphasize breadth rather than depth. The goal is to provide readers with a brief introduction to many topics, so that they will have an idea of what's 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. Readers 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 readers become skillful at making productive use of computational techniques. They should learn to use computational modes of thoughts to frame problems, to build computational models, 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.

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 more challenging, and are suitable for exam questions. And others are challenging enough to be useful as homework assignments.

Chapters 1-13 contain the kind of material typically included in an introductory computer science course, but the presentation is not conventional. We braid together four strands of material:

• The basics of programming,
• The Python 3 programming language,
• Computational problem solving techniques, and
• Computational complexity.

We cover most of Python's 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 Chapter 3, 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 readers learn Python and how to be a good programmer in the context of using computation to solve interesting problems. These chapters have been revised to proceed more gently and include more excercises than the corresponding chapters in the second edition of this book.

Chapter 13 contains an introduction to plotting in Python. This topic is often not covered in introductory courses, but we believe that learning to produce visualizations of information is an important skill that should be included in an introductory computer science course. This chapter includes material not covered in the second edition.

Chapters 14-26 are about using computation to help understand the real world. They cover material that we think should become the usual second course in a computer science curriculum. They assume no knowledge of mathematics beyond high school algebra, but do assume that the reader is comfortable with rigorous thinking and is not intimidated by mathematical concepts.

This part of the book is devoted to topics not found in most introductory texts: data visualization and analysis, stochastic programs, simulation models, probabilistic and statistical thinking, and machine learning. We believe that this is a far more relevant body of material for most students than what is typically covered in the second computer science course. Except for Chapter 23, the material in this section of the book focuses on conceptual issues rather than programming. Chapter 23 is an introduction to Pandas, a topic not covered in earlier editions.

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 don't 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.

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 complete the finger excercises that involve coding. If you are up for trying more ambitious tasks, try some of the problem sets available through

and