Computer Science A Chapman & Hall/CRC C O TEXTBOOKS IN COMPUTING N C I S Suitable for newcomers to computer science, A Concise Introduc- E A CONCISE INTRODUCTION tion to Programming in Python provides a succinct, yet complete, IN first course in computer science using the Python programming lan- T R TO PROGRAMMING IN guage. O D The book features: U PYTHON C • Short, modular chapters with brief and precise explanations, T I intended for one class period O N • Early introduction of basic procedural constructs such as T functions, selection, and repetition, allowing them to be used O throughout the course P R • Objects are introduced in the middle of the course, and class O G design comes toward the end R A • Examples, exercises, and projects from a wide range of M application domains, including biology, physics, images, sound, M mathematics, games, and textual analysis IN G • No external libraries are required, simplifying the book’s use in I common lab spaces N P Each chapter introduces a main idea through a concrete example and Y T a series of exercises. Designed to teach programming in a concise, H O yet comprehensive way, this book provides a timely introduction for N students and anyone interested in learning Python. J o h n s o n Mark J. Johnson K14279 K14279_Cover.indd 1 11/28/11 3:57 PM A CONCISE INTRODUCTION TO PROGRAMMING IN PYTHON CHAPMAN & HALL/CRC TEXTBOOKS IN COMPUTING Series Editors John Impagliazzo Andrew McGettrick Professor Emeritus, Hofstra University Department of Computer and Information Sciences University of Strathclyde Aims and Scope This series covers traditional areas of computing, as well as related technical areas, such as software engineering, artificial intelligence, computer engineering, information systems, and information technology. The series will accommodate textbooks for undergraduate and gradu- ate students, generally adhering to worldwide curriculum standards from professional societ- ies. The editors wish to encourage new and imaginative ideas and proposals, and are keen to help and encourage new authors. The editors welcome proposals that: provide groundbreaking and imaginative perspectives on aspects of computing; present topics in a new and exciting context; open up opportunities for emerging areas, such as multi-media, security, and mobile systems; capture new developments and applications in emerging fields of computing; and address topics that provide support for computing, such as mathematics, statistics, life and physical sciences, and business. Published Titles Pascal Hitzler, Markus Krötzsch, and Sebastian Rudolph, Foundations of Semantic Web Technologies Uvais Qidwai and C.H. Chen, Digital Image Processing: An Algorithmic Approach with MATLAB® Henrik Bærbak Christensen, Flexible, Reliable Software: Using Patterns and Agile Development John S. Conery, Explorations in Computing: An Introduction to Computer Science Lisa C. Kaczmarczyk, Computers and Society: Computing for Good Mark J. Johnson, A Concise Introduction to Programming in Python Chapman & Hall/CRC TEXTBOOKS IN COMPUTING A CONCISE INTRODUCTION TO PROGRAMMING IN PYTHON Mark J. Johnson CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2012 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20111110 International Standard Book Number-13: 978-1-4398-9695-2 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information stor- age or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copy- right.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that pro- vides licenses and registration for a variety of users. For organizations that have been granted a pho- tocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com Contents Code Listings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Part I Foundations 1 1 Computer Systems and Software . . . . . . . . . . . . . . . . 3 2 Python Program Components . . . . . . . . . . . . . . . . . 7 3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4 Repetition: For Loops . . . . . . . . . . . . . . . . . . . . . . 19 5 Computer Memory: Integers . . . . . . . . . . . . . . . . . . 25 6 Selection: If Statements . . . . . . . . . . . . . . . . . . . . . 29 7 Algorithm Design and Debugging . . . . . . . . . . . . . . . 37 8 Repetition: While Loops . . . . . . . . . . . . . . . . . . . . 41 Project: Newton’s Method . . . . . . . . . . . . . . . . . . . 47 9 Computer Memory: Floats . . . . . . . . . . . . . . . . . . . 49 10 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Project: Visualization . . . . . . . . . . . . . . . . . . . . . . 57 Part II Collections and Files 59 11 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 12 Building Strings . . . . . . . . . . . . . . . . . . . . . . . . . 65 Project: ISBN Check Digits . . . . . . . . . . . . . . . . . . . 71 13 Computer Memory: Text . . . . . . . . . . . . . . . . . . . . 73 14 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Project: Program Performance . . . . . . . . . . . . . . . . . 83 Project: Heat Diffusion . . . . . . . . . . . . . . . . . . . . . 85 15 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 16 String Methods . . . . . . . . . . . . . . . . . . . . . . . . . 93 Project: File Compression . . . . . . . . . . . . . . . . . . . . 101 17 Mutable and Immutable Objects . . . . . . . . . . . . . . . . 103 Project: Hangman . . . . . . . . . . . . . . . . . . . . . . . . 107 18 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Project: ELIZA . . . . . . . . . . . . . . . . . . . . . . . . . 115 Project: Shannon Entropy . . . . . . . . . . . . . . . . . . . 117 Project: Reading DNA Frames . . . . . . . . . . . . . . . . . 119 v vi Contents Part III Selected Topics 121 19 Sound Manipulation . . . . . . . . . . . . . . . . . . . . . . . 123 20 Sound Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 129 21 Image Manipulation . . . . . . . . . . . . . . . . . . . . . . . 135 Project: Image Filters . . . . . . . . . . . . . . . . . . . . . . 143 22 Image Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 147 23 Writing Classes . . . . . . . . . . . . . . . . . . . . . . . . . 153 24 Cooperating Classes . . . . . . . . . . . . . . . . . . . . . . . 159 Case Study: PPM Image Class . . . . . . . . . . . . . . . . . 165 25 Related Classes . . . . . . . . . . . . . . . . . . . . . . . . . 169 26 Functional Programming . . . . . . . . . . . . . . . . . . . . 175 27 Parallel Programming . . . . . . . . . . . . . . . . . . . . . . 181 28 Graphical User Interfaces . . . . . . . . . . . . . . . . . . . . 185 Bibliography 193 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Code Listings 1.1 Area of a Circle . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Mad Lib® . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1 Hypotenuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1 Harmonic Sum . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.1 Centipede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 8.1 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 41 8.2 Newton’s Method (Algorithm) . . . . . . . . . . . . . . . . . 47 10.1 Monte Carlo Integration . . . . . . . . . . . . . . . . . . . . . 52 11.1 Pig Latin Translation . . . . . . . . . . . . . . . . . . . . . . 61 12.1 DNA Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . 65 14.1 Sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . . . . 75 14.2 Heat Diffusion (Algorithm) . . . . . . . . . . . . . . . . . . . 85 15.1 Solve Jumble™ . . . . . . . . . . . . . . . . . . . . . . . . . . 87 16.1 GCS Menu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 18.1 Word Frequency . . . . . . . . . . . . . . . . . . . . . . . . . 109 19.1 Reverse WAV . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 20.1 Synthesizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 21.1 Two-Tone Image . . . . . . . . . . . . . . . . . . . . . . . . . 135 22.1 Mandelbrot Set . . . . . . . . . . . . . . . . . . . . . . . . . . 147 23.1 Sum of Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 24.1 Chuck-a-Luck . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 24.2 Dice Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 24.3 ImagePPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 25.1 Sierpinski Triangle . . . . . . . . . . . . . . . . . . . . . . . . 169 26.1 Word Frequency (Functional Version) . . . . . . . . . . . . . 175 27.1 Monte Carlo Integration (Parallel Version) . . . . . . . . . . . 181 28.1 Chuck-a-Luck (GUI Version) . . . . . . . . . . . . . . . . . . 185 28.2 Dice GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 vii TThhiiss ppaaggee iinntteennttiioonnaallllyy lleefftt bbllaannkk Preface Welcome! ThistextprovidesanintroductiontowritingsoftwareinPython.Noprevious programming experience is necessary. Most chapters begin with an example program illustrating a small set of new concepts. These programs are available for download at http://www.central .edu/go/conciseintro/. However, you might consider typing each program in by hand rather than using the downloaded files. The reason is that you can learn by typing, both in terms of thoroughly reading the programs, and responding to error messages that result from typos. Rather than being a hindrance, learning to deal with error messages will be quite helpful as you write your own programs. To Instructors This text is designed for a first course in computer science and is suitable for majors and non-majors. Among its features: • Chapters are short, intended for one or at most two class periods. This provides a flexible framework to build a course around. • Explanations are brief and precise. • Basic procedural constructs such as functions, selection, and repetition areintroducedearly,allowingthemtobeusedthroughoutthesemester. • Objects are (explicitly) used in the middle of the course, and writing classes comes toward the end. • Examples, exercises, and projects are from a wide range of application domains,includingbiology,physics,images,sound,mathematics,games, and textual analysis. • Noexternallibrariesarerequired.Allexampleprogramsruninstandard Python 3. This text is designed to help teach programming rather than being an ency- clopedic reference. Topics are introduced as needed for the examples, and the focusisalwaysonwhatabeginningstudentmightneedtoknowatthatpoint. ix