Introduction to programming using python daniel liang pdf

Python Programming Problems

Thank you for purchasing a new copy of Introduction to Programming Using Python. Your textbook includes six months of prepaid access to the book’s Companion Website. This prepaid subscription provides you with full access to the following student support areas:

ming concepts presented in this textbook.

Use a coin to scratch off the coating and reveal your student access code. Do not use a knife or other sharp object as it may damage the code.

To access the Introduction to Programming Using Python Companion Website for the

a web browser. The process takes just a couple of minutes and only needs to be completed once.

1. Go to http://www.pearsonhighered.com/liang

2. Click on Companion Website.

3. Click on the Register button.

4. *

5. Need Help? icon.

6. Introduction to Programming Using Python Companion Website!

To log in after you have registered:

time at http://www.pearsonhighered.com/liang

*

http:// www.pearsonhighered.com/liang

http://www.pearsonhighered.com/liang
http://www.pearsonhighered.com/liang
http://www.pearsonhighered.com/liang
http://www.pearsonhighered.com/liang
ALWAYS LEARNING PEARSON

Learn more at www.myprogramminglab.com

MyProgrammingLab™

Through the power of practice and immediate personalized

feedback, MyProgrammingLab improves your performance.

get with the programming

www.myprogramminglab.com
This page intentionally left blank

Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto

Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo

INTRODUCTION TO PROGRAMMING USING

PYTHON

Y. Daniel Liang Armstrong Atlantic State University

Editorial Director, ECS: Marcia Horton Editor-in-Chief: Michael Hirsch Executive Editor: Tracy Dunkelberger Associate Editor: Carole Snyder Director of Marketing: Patrice Jones Marketing Manager: Yezan Alayan Marketing Coordinator: Kathryn Ferranti Director of Production: Vince O’Brien Managing Editor: Jeff Holcomb Production Project Manager: Heather McNally Manufacturing Buyer: Lisa McDowell Art Director and Cover Designer: Anthony Gemmellaro Text Designer: Gillian Hall Cover Art: “Life Aquatic” © Arthur Xanthopoulos from Damaged Photography Media Editor: Daniel Sandin Full-Service Project Management: Gillian Hall Composition: Laserwords Printer/Binder: Edwards Brothers Cover Printer: Lehigh-Phoenix Color/Hagerstown

Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on Credits page located in the end matter.

Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other coun- tries. Screen shots and icons reprinted with permission from the Microsoft Corporation. This book is not sponsored or endorsed by or affiliated with the Microsoft Corporation.

Copyright © 2013 Pearson Education, Inc., publishing as Prentice Hall. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290.

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data��������

10 9 8 7 6 5 4 3 2 1

ISBN 13: 978-0-13-274718-9 ISBN 10: 0-13-274718-9

www.pearsonhighered.com
This book is dedicated to my former colleagues at the National Severe Storms Laboratory,

in Norman, Oklahoma.

To Samantha, Michael, and Michelle

vi

PREFACE Dear Reader,

This book assumes that you are a new programmer with no prior knowledge of programming. So, what is programming? Programming solves problems by creating solutions—writing programs—in a programming language. The fundamentals of problem solving and programming are the same regardless of which programming language you use. You can learn programming using any high-level programming language such as Python, Java, C++, or C#. Once you know how to program in one language, it is easy to pick up other languages, because the basic tech- niques for writing programs are the same.

So what are the benefits of learning programming using Python? Python is easy to learn and fun to program. Python code is simple, short, readable, intuitive, and powerful, and thus it is effective for introducing computing and problem solving to beginners.

Beginners are motivated to learn programming so they can create graphics. A big reason for learning programming using Python is that you can start programming using graphics on day one. We use Python’s built-in Turtle graphics module in Chapters 1–6 because it is a good pedagogical tool for introducing fundamental concepts and techniques of programming. We introduce Python’s built-in Tkinter in Chapter 9, because it is a great tool for developing comprehensive graphical user interfaces and for learning object-oriented programming. Both Turtle and Tkinter are remarkably simple and easy to use. More importantly, they are valuable pedagogical tools for teaching the fundamentals of programming and object-oriented programming.

To give instructors flexibility to use this book, we cover Turtle at the end of Chapters 1–6 so they can be skipped as optional material.

The book teaches problem solving in a problem-driven way that focuses on problem solv- ing rather than syntax. We stimulate student interests in programming by using interesting examples in a broad context. While the central thread of the book is on problem solving, appropriate Python syntax and library are introduced in order to solve the problems. To sup- port the teaching of programming in a problem-driven way, the book provides a wide variety of problems at various levels of difficulty to motivate students. In order to appeal to students in all majors, the problems cover many application areas in math, science, business, financial management, gaming, animation, and multimedia.

All data in Python are objects. We introduce and use objects from Chapter 3, but defining custom classes are covered in the middle of the book starting from Chapter 7. The book focuses on fundamentals first: it introduces basic programming concepts and techniques on selections, loops, and functions before writing custom classes.

The best way to teach programming is by example, and the only way to learn programming is by doing. Basic concepts are explained by example and a large number of exercises with various levels of difficulty are provided for students to practice. Our goal is to produce a text that teaches problem solving and programming in a broad context using a wide variety of interesting examples and exercises.

Sincerely,

Y. Daniel Liang y.daniel.liang@gmail.com www.cs.armstrong.edu/liang www.pearsonhighered.com/liang

what is programming?

why Python?

graphics

optional Turtle

problem-driven

fundamentals first

examples and exercises

www.cs.armstrong.edu/liang
www.pearsonhighered.com/liang
Preface vii

Pedagogical Features The book uses the following elements to get the most from the material:

■ Objectives list what students should learn in each chapter. This will help them determine whether they have met the objectives after completing the chapter.

■ The Introduction opens the discussion with representative problems to give the reader an overview of what to expect from the chapter.

■ Key Points highlight the important concepts covered in each section.

■ Check Points provide review questions to help students track their progress and evaluate their learning.

■ Problems, carefully chosen and presented in an easy-to-follow style, teach problem solving and programming concepts. The book uses many small, simple, and stimulating examples to demonstrate important ideas.

■ Key Terms are listed with a page number to give students a quick reference to the impor- tant terms introducd in the chapter.

■ The Chapter Summary reviews the important subjects that students should understand and remember. It helps them reinforce the key concepts they have learned in the chapter.

■ Test Questions are available online, grouped by sections for students to do self-test on programming concepts and techniques.

■ Programming Exercises are grouped by sections to provide students with opportunities to apply on their own the new skills they have learned. The level of difficulty is rated as easy (no asterisk), moderate (*), hard (**), or challenging (***). The trick of learning programming is practice, practice, and practice. To that end, the book provides a great many exercises.

■ Notes, Tips, and Cautions are inserted throughout the text to offer valuable advice and insight on important aspects of program development.

Note Provides additional information on the subject and reinforces important concepts.

Tip Teaches good programming style and practice.

Caution Helps students steer away from the pitfalls of programming errors.

Flexible Chapter Orderings Graphics is a valuable pedagogical tool for learning programming. The book uses Turtle graphics in Chapters 1–6 and Tkinter in the rest of the book. However, the book is designed to give the instructors the flexibility to skip the sections on graphics or to cover them later. The following diagram shows the chapter dependencies.

Chapter 10, Lists can be covered right after Chapter 6, Functions. Chapter 14, Tuples, Sets, and Dictionaries can be covered after Chapter 10.

viii Preface

Organization of the Book The chapters can be grouped into three parts that, taken together, form a comprehensive intro- duction to Python programming. Because knowledge is cumulative, the early chapters pro- vide the conceptual basis for understanding programming and guide students through simple examples and exercises; subsequent chapters progressively present Python programming in detail, culminating with the development of comprehensive applications.

Part I: Fundamentals of Programming (Chapters 1–6)

The first part of the book is a stepping stone, preparing you to embark on the journey of learn- ing programming. You will begin to know Python (Chapter 1) and will learn fundamental pro- gramming techniques with data types, variables, constants, assignments, expressions, operators, objects, and simple functions and string operations (Chapters 2–3), selection state- ments (Chapter 4), loops (Chapter 5), and functions (Chapter 6).

Part II: Object-Oriented Programming (Chapters 7–13)

This part introduces object-oriented programming. Python is an object-oriented programming language that uses abstraction, encapsulation, inheritance, and polymorphism to provide great flexibility, modularity, and reusability in developing software. You will learn object-oriented programming (Chapters 7–8), GUI programming using Tkinter (Chapter 9), lists (Chapter 10), multidimensional lists (Chapter 11), inheritance, polymorphism, and class design (Chapter 12), and files and exception handling (Chapter 13).

Part III: Data Structures and Algorithms (Chapters 14–15 and Bonus Chapters 16–23)

This part introduces the main subjects in a typical data structures course. Chapter 14 intro- duces Python built-in data structures: tuples, sets, and dictionaries. Chapter 15 introduces

Chapter 10 Lists

Chapter 4 Selections

Chapter 5 Loops

Chapter 1 Introduction to Computers, Programs, and Python

Chapter 2 Elementary Programming

Chapter 7 Objects and Classes

Chapter 13 Files and Exception Handling

Note: Chapters 16–23 are bonus chapters available from the Companion Website

Chapter 8 More on Strings and Special Methods

Chapter 9 GUI Programming Using Tkinter

Chapter 11 Multidimensional Lists

Chapter 12 Inheritance and Polymorphism

Chapter 14 Tuples, Sets, and Dictionaries

Chapter 15 Recursion

Chapter 16 Developing Efficient Algorithms

Chapter 17 Sorting

Chapter 18 Linked Lists, Stacks, Queues, and Priority Queues

Chapter 19 Binary Search Trees

Chapter 20 AVL Trees

Chapter 21 Hashing: Implementing Dictionaries and Sets

Chapter 22 Graphs and Applications

Chapter 23 Weighted Graphs and Applications

Part I: Fundamentals of Programming

Part II: Object-Oriented Programming

Part III: Data Structures and Algorithms

Chapter 3 Mathematical Functions, Strings, and Objects

Chapter 6 Functions

Preface ix

recursion to write functions for solving inherently recursive problems. Chapters 16–23 are bonus chapters on the Companion Website. Chapter 16 introduces measurement of algorithm efficiency and common techniques for developing efficient algorithms. Chapter 17 discusses classic sorting algorithms. You will learn how to implement linked lists, queues, and priority queues in Chapter 18. Chapter 19 presents binary search trees, and you will learn about AVL trees in Chapter 20. Chapter 21 introduces hashing, and Chapters 22 and 23 cover graph algo- rithms and applications.

Student Resource Website The Student Resource Website (www.cs.armstrong.edu/liang/py) contains the following resources:

■ Answers to review questions

■ Solutions to even-numbered programming exercises

■ Source code for the examples in the book

■ Interactive self-test questions (organized by sections for each chapter)

■ Supplements on using Python IDEs, advanced topics, etc.

■ Resource links

■ Errata

Additional Supplements The text covers the essential subjects. The supplements extend the text to introduce additional topics that might be of interest to readers. The supplements listed in this table are available from the Companion Website.

Part I. General Supplements A. Glossary B. Installing and Using Python C. Python IDLE D. Python on Eclipse E. Python on Eclipse Debugging F. Python Coding Style Guidelines

Part II. Advanced Python Topics A. Regular Expressions B. Obtaining Date and Time C. The str Class’s format Method D. Pass Arguments from Command Line E. Database Programming

Instructor Resource Website The Instructor Resource Website, accessible from www.cs.armstrong.edu/liang/py, contains the following resources:

■ Microsoft PowerPoint slides with interactive buttons to view full-color, syntax-highlighted source code and to run programs without leaving the slides.

■ Solutions to all the review questions and exercises. Students will have access to the solu- tions of even-numbered programming exercises.

■ Web-based quiz generator. (Instructors can choose chapters to generate quizzes from a large database of more than 800 questions.)

www.cs.armstrong.edu/liang/py
www.cs.armstrong.edu/liang/py
x Preface

■ Sample exams. In general, each exam has four parts:

■ Multiple-choice questions or short-answer questions

■ Correct programming errors

■ Trace programs

■ Write programs

■ Projects. In general, each project gives a description and asks students to analyze, design, and implement the project.

Some readers have requested the materials from the Instructor Resource Website. Please understand that these are for instructors only. Such requests will not be answered.

Online Practice and Assessment with MyProgrammingLab MyProgrammingLab helps students fully grasp the logic, semantics, and syntax of program- ming. Through practice exercises and immediate, personalized feedback, MyProgrammingLab improves the programming competence of beginning students who often struggle with the basic concepts and paradigms of popular high-level programming languages.

A self-study and homework tool, a MyProgrammingLab course consists of hundreds of small practice problems organized around the structure of this textbook. For students, the system automatically detects errors in the logic and syntax of their code submissions and offers targeted hints that enable students to figure out what went wrong—and why. For instructors, a comprehensive gradebook tracks correct and incorrect answers and stores the code inputted by students for review.

MyProgrammingLab is offered to users of this book in partnership with Turing’s Craft, the makers of the CodeLab interactive programming exercise system. For a full demonstration, to see feedback from instructors and students, or to get started using MyProgrammingLab in your course, visit www.myprogramminglab.com.

VideoNotes VideoNotes are Pearson’s new visual tool designed for teaching students key programming con- cepts and techniques. These short step-by-step videos demonstrate how to solve problems from design through coding. VideoNotes allow for self-placed instruction with easy navigation includ- ing the ability to select, play, rewind, fast-forward, and stop within each VideoNote exercise.

Margin icons in your textbook let you know when a VideoNote video is available for a par- ticular concept or homework problem.

LiveLab This book is accompanied by a complementary Web-based course assessment and manage- ment system for instructors. The system has four main components:

■ The Automatic Grading System can automatically grade programs.

■ The Quiz Creation/Submission/Grading System enables instructors to create and mod- ify quizzes that students can take and be graded upon automatically.

■ The Peer Evaluation System enables peer evaluations.

■ Checking plagiarisms, tracking grades, attendance, etc., lets students track their grades, and enables instructors to view the grades of all students, to check plagiarisms, and to track students’ attendance.

VideoNote

www.myprogramminglab.com
Preface xi

The main features of the Automatic Grading System include:

■ Students can run and submit exercises. (The system checks whether their program runs correctly—students can continue to run and resubmit the program before the due date.)

■ Instructors can review submissions, run programs with instructor test cases, correct them, and provide feedback to students.

■ Instructors can create/modify their own exercises, create public and secret test cases, as- sign exercises, and set due dates for the whole class or for individuals.

■ All the exercises in the text can be assigned to students. Additionally, LiveLab provides extra exercises that are not printed in the text.

■ Instructors can sort and filter all exercises and check grades (by time frame, student, and/or exercise).

■ Instructors can check plagiarisms for a programming exercise.

■ Instructors can delete students from the system.

■ Students and instructors can track grades on exercises.

The main features of the Quiz System are:

■ Instructors can create/modify quizzes from the test bank or a text file or create completely new tests online.

■ Instructors can assign the quizzes to students and set a due date and test time limit for the whole class or for individuals.

■ Students and instructors can review submitted quizzes.

■ Instructors can analyze quizzes and identify students’ weaknesses.

■ Students and instructors can track grades on quizzes.

The main features of the Peer Evaluation System include:

■ Instructors can assign/unassign exercises for peer evaluation.

■ Instructors can view peer evaluation reports.

Acknowledgments I would like to thank Armstrong Atlantic State University for enabling me to teach what I write and for supporting me in writing what I teach. Teaching is the source of inspiration for the book. I am grateful to the instructors and students who have offered comments, sugges- tions, bug reports, and praise.

This book has been greatly enhanced thanks to the outstanding reviewers. They are:

Claude Anderson – Rose-Hulman Institute of Technology Lee Cornell – Minnesota State University – Mankato John Magee – Boston University Shyamal Mitra – University of Texas – Austin Yenumula Reddy – Grambling State University David Sullivan – Boston University Hong Wang – University of Toledo

It is a great pleasure, honor, and privilege to work with Pearson. I would like to thank Tracy Dunkelberger, Marcia Horton, Michael Hirsch, Matt Goldstein, Carole Snyder, Tim Huddleston, Yez Alayan, Jeff Holcomb, Gillian Hall, Rebecca Greenberg, and their colleagues for organizing, producing, and promoting this project.

As always, I am indebted to my wife, Samantha, for her love, support, and encouragement.

BRIEF CONTENTS 1 Introduction to Computers, Programs,

and Python 1

2 Elementary Programming 31

3 Mathematical Functions, Strings, and Objects 63

4 Selections 91

5 Loops 133

6 Functions 171

7 Objects and Classes 215

8 More on Strings and Special Methods 241

9 GUI Programming Using Tkinter 271

10 Lists 313

11 Multidimensional Lists 361

12 Inheritance and Polymorphism 399

13 Files and Exception Handling 439

14 Tuples, Sets, and Dictionaries 475

15 Recursion 499

xii

Chapters 16–23 are bonus Web chapters

16 Developing Efficient Algorithms 16-1 17 Sorting 17-1 18 Linked Lists, Stacks, Queues,

and Priority Queues 18-1

19 Binary Search Trees 19-1 20 AVL Trees 20-1 21 Hashing: Implementing Dictionaries

and Sets 21-1

22 Graphs and Applications 22-1 23 Weighted Graphs and Applications 23-1

APPENDIXES A Python Keywords 533 B The ASCII Character Set 534 C Number Systems 536

INDEX 541

CREDITS 557

CONTENTS Chapter 1 Introduction to Computers, Programs,

and Python 1 1.1 Introduction 2 1.2 What Is a Computer? 2 1.3 Programming Languages 9 1.4 Operating Systems 12 1.5 The History of Python 13 1.6 Getting Started with Python 14 1.7 Programming Style and Documentation 18 1.8 Programming Errors 19 1.9 Getting Started with Graphics Programming 21

Chapter 2 Elementary Programming 31 2.1 Introduction 32 2.2 Writing a Simple Program 32 2.3 Reading Input from the Console 34 2.4 Identifiers 36 2.5 Variables, Assignment Statements, and Expressions 36 2.6 Simultaneous Assignments 38 2.7 Named Constants 39 2.8 Numeric Data Types and Operators 40 2.9 Evaluating Expressions and Operator Precedence 43

2.10 Augmented Assignment Operators 44 2.11 Type Conversions and Rounding 45 2.12 Case Study: Displaying the Current Time 46 2.13 Software Development Process 48 2.14 Case Study: Computing Distances 52

Chapter 3 Mathematical Functions, Strings, and Objects 63

3.1 Introduction 64 3.2 Common Python Functions 64 3.3 Strings and Characters 67 3.4 Case Study: Minimum Number of Coins 72 3.5 Introduction to Objects and Methods 74 3.6 Formatting Numbers and Strings 76 3.7 Drawing Various Shapes 81 3.8 Drawing with Colors and Fonts 83

xiii

Chapter 4 Selections 91 4.1 Introduction 92 4.2 Boolean Types, Values, and Expressions 92 4.3 Generating Random Numbers 93 4.4 if Statements 95 4.5 Case Study: Guessing Birthdays 96 4.6 Two-Way if-else Statements 100 4.7 Nested if and Multi-Way if-elif-else Statements 102 4.8 Common Errors in Selection Statements 105 4.9 Case Study: Computing Body Mass Index 107

4.10 Case Study: Computing Taxes 108 4.11 Logical Operators 110 4.12 Case Study: Determining Leap Years 113 4.13 Case Study: Lottery 114 4.14 Conditional Expressions 116 4.15 Operator Precedence and Associativity 117 4.16 Detecting the Location of an Object 118

Chapter 5 Loops 133 5.1 Introduction 134 5.2 The while Loop 134 5.3 The for Loop 143 5.4 Nested Loops 145 5.5 Minimizing Numerical Errors 147 5.6 Case Studies 148 5.7 Keywords break and continue 151 5.8 Case Study: Displaying Prime Numbers 154 5.9 Case Study: Random Walk 156

Chapter 6 Functions 171 6.1 Introduction 172 6.2 Defining a Function 172 6.3 Calling a Function 173 6.4 Functions with/without Return Values 176 6.5 Positional and Keyword Arguments 179 6.6 Passing Arguments by Reference Values 180 6.7 Modularizing Code 183 6.8 Case Study: Converting Decimals to Hexadecimals 185 6.9 The Scope of Variables 187

6.10 Default Arguments 189 6.11 Returning Multiple Values 190 6.12 Case Study: Generating Random ASCII Characters 191 6.13 Function Abstraction and Stepwise Refinement 192 6.14 Case Study: Reusable Graphics Functions 199

xiv Contents

Chapter 7 Objects and Classes 215 7.1 Introduction 216 7.2 Defining Classes for Objects 216 7.3 UML Class Diagrams 222 7.4 Immutable Objects vs. Mutable Objects 225 7.5 Hiding Data Fields 227 7.6 Class Abstraction and Encapsulation 229 7.7 Object-Oriented Thinking 233

Chapter 8 More on Strings and Special Methods 241 8.1 Introduction 242 8.2 The str Class 242 8.3 Case Study: Checking Palindromes 253 8.4 Case Study: Converting Hexadecimals to Decimals 254 8.5 Operator Overloading and Special Methods 257 8.6 Case Study: The Rational Class 258

Chapter 9 GUI Programming Using Tkinter 271 9.1 Introduction 272 9.2 Getting Started with Tkinter 272 9.3 Processing Events 273 9.4 The Widget Classes 275 9.5 Canvas 280 9.6 The Geometry Managers 283 9.7 Case Study: Loan Calculator 287 9.8 Displaying Images 288 9.9 Menus 290

9.10 Popup Menus 292 9.11 Mouse, Key Events, and Bindings 294 9.12 Animations 297 9.13 Scrollbars 300 9.14 Standard Dialog Boxes 301

Chapter 10 Lists 313 10.1 Introduction 314 10.2 List Basics 315 10.3 Case Study: Lotto Numbers 325 10.4 Case Study: Deck of Cards 327 10.5 Deck of Cards GUI 329 10.6 Copying Lists 330 10.7 Passing Lists to Functions 332 10.8 Returning a List from a Function 334 10.9 Case Study: Counting the Occurrences of Each Letter 335

10.10 Searching Lists 338

Contents xv

10.11 Sorting Lists 341 10.12 Case Study: Bouncing Balls 345

Chapter 11 Multidimensional Lists 361 11.1 Introduction 362 11.2 Processing Two-Dimensional Lists 362 11.3 Passing Two-Dimensional Lists to Functions 365 11.4 Problem: Grading a Multiple-Choice Test 367 11.5 Problem: Finding the Closest Pair 368 11.6 GUI: Finding the Closest Pair 370 11.7 Problem: Sudoku 372 11.8 Case Study: Sudoku GUI 375 11.9 Multidimensional Lists 377

Chapter 12 Inheritance and Polymorphism 399 12.1 Introduction 400 12.2 Superclasses and Subclasses 400 12.3 Overriding Methods 405 12.4 The object Class 406 12.5 Polymorphism and Dynamic Binding 409 12.6 The isinstance Function 411 12.7 Case Study: A Reusable Clock 414 12.8 Class Relationships 418 12.9 Case Study: Designing the Course Class 421

12.10 Designing a Class for Stacks 423 12.11 Case Study: The FigureCanvas Class 425

Chapter 13 Files and Exception Handling 439 13.1 Introduction 440 13.2 Text Input and Output 440 13.3 File Dialogs 448 13.4 Case Study: Counting Each Letter in a File 451 13.5 Retrieving Data from the Web 452 13.6 Exception Handling 454 13.7 Raising Exceptions 457 13.8 Processing Exceptions Using Exception Objects 460 13.9 Defining Custom Exception Classes 460

13.10 Binary IO Using Pickling 465 13.11 Case Study: Address Book 467

Chapter 14 Tuples, Sets, and Dictionaries 475 14.1 Introduction 476 14.2 Tuples 476 14.3 Sets 479 14.4 Comparing the Performance of Sets and Lists 485

xvi Contents

14.5 Case Study: Counting Keywords 486 14.6 Dictionaries 487 14.7 Case Study: Occurrences of Words 492

Chapter 15 Recursion 499 15.1 Introduction 500 15.2 Case Study: Computing Factorials 500 15.3 Case Study: Computing Fibonacci Numbers 503 15.4 Problem Solving Using Recursion 505 15.5 Recursive Helper Functions 507 15.6 Case Study: Finding the Directory Size 510 15.7 Case Study: Towers of Hanoi 512 15.8 Case Study: Fractals 515 15.9 Case Study: Eight Queens 518

15.10 Recursion vs. Iteration 520 15.11 Tail Recursion 521

A detailed table of contents for the Web chapters is available on the companion Website:

Chapter 16 Developing Efficient Algorithms 16–1

Chapter 17 Sorting 17–1

Chapter 18 Linked Lists, Stacks, Queues, and Priority Queues 18–1

Chapter 19 Binary Search Trees 19–1

Chapter 20 AVL Trees 20–1

Chapter 21 Hashing: Implementing Dictionaries and Sets 21–1

Chapter 22 Graphs and Applications 22-1

Chapter 23 Weighted Graphs and Applications 23-1

APPENDIXES

Appendix A Python Keywords 533 Appendix B The ASCII Character Set 534 Appendix C Number Systems 536

INDEX 541

CREDITS 557

Contents xvii

LOCATION OF VIDEONOTES IN THE TEXT

Chapter 1 Start with Python, p. 14 Start with Turtle graphics, p. 21

Chapter 2 Assignment statement, p. 37 Perform computation, p. 40

Chapter 3 String operations, p. 75 Draw shapes, p. 81

Chapter 4 Boolean expressions, p. 92 Coffee price, p. 123

Chapter 5 while loop, p. 134 for loop, p. 143

Chapter 6 Use functions, p. 172 Divide and conquer, p. 192

Chapter 7 Define and use classes, p. 217 Private data fields, p. 227

Chapter 8 String methods, p. 242 Define classes, p. 258

Chapter 9 Simple GUI, p. 273 Create GUI application, p. 287

Chapter 10 Use lists, p. 315 Search a list, p. 338

Chapter 11 Process a matrix, p. 362 Chessboard, p. 394

Chapter 12 Inheritance and polymorphism, p. 400 Dynamic binding, p. 409

Chapter 13 Process text file, p. 443 Handle exceptions, p. 454

Chapter 14 Use sets, p. 479 Use dictionaries, p. 488

Chapter 15 Function sum, p. 500 Function print numbers, p. 506

xviii Location of VideoNotes in the Text

INTRODUCTION TO COMPUTERS, PROGRAMS, AND PYTHON

Objectives ■ To demonstrate a basic understanding of computer hardware,

programs, and operating systems (§§1.2–1.4).

■ To describe the history of Python (§1.5).

■ To explain the basic syntax of a Python program (§1.6).

■ To write and run a simple Python program (§1.6).

■ To explain the importance of, and provide examples of, proper programming style and documentation (§1.7).

■ To explain the differences between syntax errors, runtime errors, and logic errors (§1.8).

■ To create a basic graphics program using Turtle (§1.9).

CHAPTER

1

2 Chapter 1 Introduction to Computers, Programs, and Python

1.1 Introduction The central theme of this book is to learn how to solve problems by writing a program.

This book is about programming. So, what is programming? The term programming means to create (or develop) software, which is also called a program. In basic terms, software contains the instructions that tell a computer—or a computerized device—what to do.

Software is all around you, even in devices that you might not think would need it. Of course, you expect to find and use software on a personal computer, but software also plays a role in running airplanes, cars, cell phones, and even toasters. On a personal computer, you use word processors to write documents, Web browsers to explore the Internet, and e-mail programs to send messages. These programs are all examples of software. Software develop- ers create software with the help of powerful tools called programming languages.

This book teaches you how to create programs by using the Python programming language. There are many programming languages, some of which are decades old. Each language was invented for a specific purpose—to build on the strengths of a previous lan- guage, for example, or to give the programmer a new and unique set of tools. Knowing that there are so many programming languages available, it would be natural for you to wonder which one is best. But, in truth, there is no “best” language. Each one has its own strengths and weaknesses. Experienced programmers know that one language might work well in some situations, whereas a different language may be more appropriate in other situations. For this reason, seasoned programmers try to master as many different programming languages as they can, giving them access to a vast arsenal of software-development tools.

If you learn to program using one language, you should find it easy to pick up other languages. The key is to learn how to solve problems using a programming approach. That is the main theme of this book.

You are about to begin an exciting journey: learning how to program. At the outset, it is helpful to review computer basics, programs, and operating systems. If you are already familiar with such terms as CPU, memory, disks, operating systems, and programming languages, you may skip the review in Sections 1.2–1.4.

1.2 What Is a Computer? A computer is an electronic device that stores and processes data.

A computer includes both hardware and software. In general, hardware comprises the visible, physical elements of the computer, and software provides the invisible instructions that control the hardware and make it perform specific tasks. Knowing computer hardware isn’t essential to learning a programming language, but it can help you better understand the effects that a program’s instructions have on the computer and its components. This section introduces com- puter hardware components and their functions.

A computer consists of the following major hardware components (Figure 1.1):

■ A central processing unit (CPU)

■ Memory (main memory)

■ Storage devices (such as disks and CDs)

■ Input devices (such as the mouse and keyboard)

■ Output devices (such as monitors and printers)

■ Communication devices (such as modems and network interface cards)

A computer’s components are interconnected by a subsystem called a bus. You can think of a bus as a sort of system of roads running among the computer’s components; data and

what is programming?

program

programming languages

hardware

software

bus

Key Point

Key Point

1.2 What Is a Computer? 3

power travel along the bus from one part of the computer to another. In personal computers, the bus is built into the computer’s motherboard, which is a circuit case that connects all of the parts of a computer together, as shown in Figure 1.2.

1.2.1 Central Processing Unit The central processing unit (CPU) is the computer’s brain. It retrieves instructions from memory and executes them. The CPU usually has two components: a control unit and an arithmetic/logic unit. The control unit controls and coordinates the actions of the other components. The arithmetic/logic unit performs numeric operations (addition, subtraction, multiplication, division) and logical operations (comparisons).

Today’s CPUs are built on small silicon semiconductor chips that contain millions of tiny electric switches, called transistors, for processing information.

Every computer has an internal clock, which emits electronic pulses at a constant rate. These pulses are used to control and synchronize the pace of operations. A higher clock speed enables more instructions to be executed in a given period of time. The unit of measurement of clock speed is the hertz (Hz), with 1 hertz equaling 1 pulse per second. In the 1990s computers measured clocked speed in megahertz, but CPU speed has been improving continuously, and

motherboard

CPU

Bus

Memory

Storage Devices

Input Devices

Output Devices

Communication Devices

FIGURE 1.1 A computer consists of a CPU, memory, storage devices, input devices, output devices, and communication devices.

CPU

speed

hertz

megahertz

4 Chapter 1 Introduction to Computers, Programs, and Python

the clock speed of a computer is now usually stated in gigahertz (GHz). Intel’s newest proces- sors run at about 3 GHz.

CPUs were originally developed with only one core. The core is the part of the processor that performs the reading and executing of instructions. In order to increase CPU processing power, chip manufacturers are now producing CPUs that contain multiple cores. A multicore CPU is a single component with two or more independent processors. Today’s consumer computers typically have two, three, and even four separate cores. Soon, CPUs with tens or even hundreds of cores will be affordable.

1.2.2 Bits and Bytes Before we discuss memory, let’s look at how information (data and programs) are stored in a computer.

A computer is really nothing more than a series of switches. Each switch exists in two states: on or off. Storing information in a computer is simply a matter of setting a sequence of switches on or off. If the switch is on, its value is 1. If the switch is off, its value is 0. These 0s and 1s are interpreted as digits in the binary number system and called bits (binary digits).

The minimum storage unit in a computer is a byte. A byte is composed of eight bits. A small number such as 3 can be stored as a single byte. To store a number that cannot fit into a single byte, the computer uses several bytes.

Data of various kinds, such as numbers and characters, are encoded as a series of bytes. As a programmer, you don’t need to worry about the encoding and decoding of data, which the computer system performs automatically, based on the encoding scheme. An encoding scheme is a set of rules that govern how a computer translates characters, numbers, and sym- bols into data the computer can actually work with. Most schemes translate each character into a predetermined string of numbers. In the popular ASCII encoding scheme, for example, the character C is represented as 01000011 in one byte.

gigahertz

core

bits

CPU is placed under the fan

Memory

Motherboard

FIGURE 1.2 The motherboard connects all parts of computer together.

byte

encoding scheme

1.2 What Is a Computer? 5

A computer’s storage capacity is measured in bytes and multiples of the byte, as follows:

■ A kilobyte (KB) is about 1,000 bytes.

■ A megabyte (MB) is about 1 million bytes.

■ A gigabyte (GB) is about 1 billion bytes.

■ A terabyte (TB) is about 1 trillion bytes.

A typical one-page word document might take 20 KB. So 1 MB can store 50 pages of doc- uments and 1 GB can store 50000 pages of documents. A typical two-hour high-resolution movie might take 8 GB. So it would require 160 GB to store 20 movies.

1.2.3 Memory A computer’s memory consists of an ordered sequence of bytes for storing programs as well as data that the program is working with. You can think of memory as the computer’s work area for executing a program. A program and its data must be moved into the computer’s memory before they can be executed by the CPU.

Every byte in the memory has a unique address, as shown in Figure 1.3. The address is used to locate the byte for storing and retrieving the data. Since the bytes in the memory can be accessed in any order, the memory is also referred to as random-access memory (RAM).

kilobyte (KB)

megabyte (MB)

gigabyte (GB)

terabyte (TB)

memory

unique address

RAM

01000011 01110010 01100101 01110111 00000011

Encoding for character ‘C’ Encoding for character ‘r’ Encoding for character ‘e’ Encoding for character ‘w’ Encoding for number 3

2000 2001 2002 2003 2004

Memory address Memory content

FIGURE 1.3 Memory stores data and program instructions in uniquely addressed memory locations. Each memory location can store one byte of data.

Today’s personal computers usually have at least 1 gigabyte of RAM, but they more com- monly have 2 to 4 GB installed. Generally speaking, the more RAM a computer has, the faster it can operate, but there are limits to this simple rule of thumb.

A memory byte is never empty, but its initial content may be meaningless to your program. The current content of a memory byte is lost whenever new information is placed in it.

Like the CPU, memory is built on silicon semiconductor chips that have millions of transistors embedded on their surface. Compared to CPU chips, memory chips are less com- plicated, slower, and less expensive.

1.2.4 Storage Devices A computer’s memory is a volatile form of data storage: any information that hasn’t been stored in memory (that is, saved) is lost when the system’s power is turned off. Programs and data are permanently stored on storage devices and are moved, when the computer actually uses them, to memory, which operates at much faster speeds than permanent storage devices can.

storage device

6 Chapter 1 Introduction to Computers, Programs, and Python

There are three main types of storage devices:

■ Magnetic disk drives

■ Optical disc drives (CD and DVD)

■ USB flash drives

Drives are devices for operating a medium, such as disks and CDs. A storage medium physi- cally stores data or program instructions. The drive reads data from the medium and/or writes data onto the medium.

Disks A computer usually has at least one hard disk drive (Figure 1.4). Hard disks are used for per- manently storing data and programs. Newer computers have hard disks that can store from 200 to 800 gigabytes of data. Hard disk drives are usually encased inside the computer, but remov- able hard disks are also available.

drive

hard disk

CD-R

CD-RW

DVD

FIGURE 1.4 A hard disk is a device for permanently storing programs and data.

CDs and DVDs CD stands for compact disc. There are two types of CD drives: CD-R and CD-RW. A CD-R is for read-only permanent storage; the user cannot modify its contents once they are recorded. A CD-RW can be used like a hard disk; that is, you can write data onto the disc, and then overwrite that data with new data. A single CD can hold up to 700 MB. Most new PCs are equipped with a CD-RW drive that can work with both CD-R and CD-RW discs.

DVD stands for digital versatile disc or digital video disc. DVDs and CDs look alike, and you can use either to store data. A DVD can hold more information than a CD; a standard DVD’s storage capacity is 4.7 GB. Like CDs, there are two types of DVDs: DVD-R (read-only) and DVD-RW (rewritable).

1.2 What Is a Computer? 7

USB Flash Drives Universal serial bus (USB) connectors allow the user to attach many kinds of peripheral devices to the computer. You can use a USB to connect a printer, digital camera, mouse, external hard disk drive, and other devices to the computer.

A USB flash drive is a device for storing and transporting data. A flash drive is small— about the size of a pack of gum, as shown in Figure 1.5. It acts like a portable hard drive that can be plugged into your computer’s USB port. USB flash drives are currently available with up to 256 GB storage capacity.

FIGURE 1.5 USB flash drives are popular portable devices for storing data.

Function

Modifier

Numeric Keypad

Page Up

Insert

Delete

Page Down

Arrows

FIGURE 1.6 A computer keyboard consists of the keys for sending input to a computer.

1.2.5 Input and Output Devices Input and output devices let the user communicate with the computer. The most common input devices are keyboards and mice. The most common output devices are monitors and printers.

The Keyboard A keyboard is a device for entering input. A typical keyboard is shown in Figure 1.6. Compact keyboards are available without a numeric keypad.

Function keys are located across the top of the keyboard and are prefaced with the letter F. Their functions depend on the software currently being used.

function key

8 Chapter 1 Introduction to Computers, Programs, and Python

A modifier key is a special key (such as the Shift, Alt, and Ctrl keys) that modifies the normal action of another key when the two are pressed simultaneously.

The numeric keypad, located on the right side of most keyboards, is a separate set of keys styled like a calculator to use for entering numbers quickly.

Arrow keys, located between the main keypad and the numeric keypad, are used to move the mouse pointer up, down, left, and right on the screen in many kinds of programs.

The Insert, Delete, Page Up, and Page Down keys are used in word processing and other programs for inserting text and objects, deleting text and objects, and moving up or down through a document one screen at a time.

The Mouse A mouse is a pointing device. It is used to move a graphical pointer (usually in the shape of an arrow) called a cursor around the screen or to click on-screen objects (such as a button) to trigger them to perform an action.

The Monitor The monitor displays information (text and graphics). The screen resolution and dot pitch determine the quality of the display.

The screen resolution specifies the number of pixels in horizontal and vertical dimensions of the display device. Pixels (short for “picture elements”) are tiny dots that form an image on the screen. A common resolution for a 17-inch screen, for example, is 1024 pixels wide and 768 pixels high. The resolution can be set manually. The higher the resolution, the sharper and clearer the image is.

The dot pitch is the amount of space between pixels, measured in millimeters. The smaller the dot pitch, the sharper the display.

1.2.6 Communication Devices Computers can be networked through communication devices, such as a dial-up modem (modulator/demodulator), a DSL or cable modem, a wired network interface card, or a wire- less adapter.

■ A dial-up modem uses a phone line and can transfer data at a speed up to 56,000 bps (bits per second).

■ A digital subscriber line (DSL) connection also uses a standard phone line, but it can transfer data 20 times faster than a standard dial-up modem.

■ A cable modem uses the cable TV line maintained by the cable company and is generally faster than DSL.

■ A network interface card (NIC) is a device that connects a computer to a local area network (LAN), as shown in Figure 1.7. LANs are commonly used in universities, businesses, and government agencies. A high-speed NIC called 1000BaseT can transfer data at 1,000 million bits per second (mbps).

■ Wireless networking is now extremely popular in homes, businesses, and schools. Every laptop computer sold today is equipped with a wireless adapter that enables the computer to connect to a local area network and the Internet.

Note Answers to checkpoint questions are on the Companion Website.

1.1 What are hardware and software? 1.2 List five major hardware components of a computer. 1.3 What does the acronym “CPU” stand for?

modifier key

numeric keypad

arrow keys

Insert key

Delete key

Page Up key Page Down key

screen resolution

pixels

dot pitch

modem

digital subscriber line (DSL)

cable modem

network interface card (NIC) local area network (LAN)

million bits per second (mbps)

✓Point✓Check

1.3 Programming Languages 9

1.4 What unit is used to measure CPU speed? 1.5 What is a bit? What is a byte? 1.6 What is memory for? What does RAM stand for? Why is memory called RAM? 1.7 What unit is used to measure memory size? 1.8 What unit is used to measure disk size? 1.9 What is the primary difference between memory and a storage device?

1.3 Programming Languages Computer programs, known as software, are instructions that tell a computer what to do.

Computers do not understand human languages, so programs must be written in a language a computer can use. There are hundreds of programming languages, and they were developed to make the programming process easier for people. However, all programs must be converted into a language the computer can understand.

1.3.1 Machine Language A computer’s native language, which differs among different types of computers, is its machine language—a set of built-in primitive instructions. These instructions are in the form of binary code, so if you want to give a computer an instruction in its native language, you have to enter

Network Interface Card

LAN

FIGURE 1.7 A local area network connects computers in close proximity to each other.

machine language

Key Point

10 Chapter 1 Introduction to Computers, Programs, and Python

the instruction as binary code. For example, to add two numbers, you might have to write an instruction in binary code, like this:

1101101010011010

1.3.2 Assembly Language Programming in machine language is a tedious process. Moreover, programs written in machine language are very difficult to read and modify. For this reason, assembly language was created in the early days of computing as an alternative to machine languages. Assembly language uses a short descriptive word, known as mnemonic, to represent each of the machine- language instructions. For example, the mnemonic add typically means to add numbers and sub means to subtract numbers. To add the numbers 2 and 3 and get the result, you might write an instruction in assembly code like this:

add 2, 3, result

Assembly languages were developed to make programming easier. However, because the computer cannot understand assembly language, another program—called an assembler—is used to translate assembly-language programs into machine code, as shown in Figure 1.8.

assembly language

assembler

Assembly Source File

... add 2, 3, result

...

Machine-Code File

... 1101101010011010

...

Assembler

FIGURE 1.8 An assembler translates assembly-language instructions into machine code.

Writing code in assembly language is easier than in machine language. However, it is still tedious to write code in assembly language. An instruction in assembly language essentially corresponds to an instruction in machine code. Writing in assembly requires that you know how the CPU works. Assembly language is referred to as a low-level language, because assembly language is close in nature to machine language and is machine dependent.

1.3.3 High-Level Language In the 1950s, a new generation of programming languages known as high-level languages emerged. They are platform-independent, which means that you can write a program in a high- level language and run it in different types of machines. High-level languages are English-like and easy to learn and use. The instructions in a high-level programming language are called statements. Here, for example, is a high-level language statement that computes the area of a circle with a radius of 5:

area = 5 * 5 * 3.1415

There are many high-level programming languages, and each was designed for a specific purpose. Table 1.1 lists some popular ones.

A program written in a high-level language is called a source program or source code. Because a computer cannot understand a source program, a source program must be translated into machine code for execution. The translation can be done using another programming tool called an interpreter or a compiler.

■ An interpreter reads one statement from the source code, translates it to the machine code or virtual machine code, and then executes it right away, as shown in Figure 1.9a.

low-level language

high-level language

source program

source code

interpreter

compiler

statement

1.3 Programming Languages 11

TABLE 1.1 Popular High-Level Programming Languages

Language Description

Ada Named for Ada Lovelace, who worked on mechanical general-purpose computers. The Ada language was developed for the Department of Defense and is used mainly in defense projects.

BASIC Beginner’s All-purpose Symbolic Instruction Code. It was designed to be learned and used easily by beginners.

C Developed at Bell Laboratories. C combines the power of an assembly language with the ease of use and portability of a high-level language.

C++ C++ is an object-oriented language, based on C.

C# Pronounced “C Sharp.” It is a hybrid of Java and C++ and was developed by Microsoft.

COBOL COmmon Business Oriented Language. Used for business applications.

FORTRAN FORmula TRANslation. Popular for scientific and mathematical applications.

Java Developed by Sun Microsystems, now part of Oracle. It is widely used for developing platform-independent Internet applications.

Pascal Named for Blaise Pascal, who pioneered calculating machines in the seventeenth century. It is a simple, structured, general-purpose language primarily for teaching programming.

Python A simple general-purpose scripting language good for writing short programs.

Visual Basic Visual Basic was developed by Microsoft and it enables the programmers to rapidly develop Windows-based applications.

Machine-Code File

... 0101100011011100 1111100011000100

...

High-Level Source File

... area = 5 * 5 * 3.1415;

...

(b)

Compiler Executor

High-Level Source File

... area = 5 * 5 * 3.1415;

...

(a)

Interpreter Output

Output

FIGURE 1.9 (a) An interpreter translates and executes a program one statement at a time. (b) A compiler translates the entire source program into a machine-language file for execution.

Note that a statement from the source code may be translated into several machine instructions.

■ A compiler translates the entire source code into a machine-code file, and the machine code file is then executed, as shown in Figure 1.9b.

Python code is executed using an interpreter. Most other programming languages are processed using a compiler.

1.10 What language does the CPU understand? 1.11 What is an assembly language? ✓Point✓Check

12 Chapter 1 Introduction to Computers, Programs, and Python

operating system (OS)

User

Application Programs

Operating System

Hardware

FIGURE 1.10 Users and applications access the computer’s hardware via the operating system.

1.12 What is an assembler? 1.13 What is a high-level programming language? 1.14 What is a source program? 1.15 What is an interpreter? 1.16 What is a compiler? 1.17 What is the difference between an interpreted language and a compiled language?

1.4 Operating Systems The operating system (OS) is the most important program that runs on a computer. The OS manages and controls a computer’s activities.

The popular operating systems for general-purpose computers are Microsoft Windows, Mac OS, and Linux. Application programs, such as a Web browser or a word processor, cannot run unless an operating system is installed and running on the computer. Figure 1.10 shows the interrelationship of hardware, operating system, application software, and the user.

The major tasks of an operating system are:

■ Controlling and monitoring system activities

■ Allocating and assigning system resources

■ Scheduling operations

1.4.1 Controlling and Monitoring System Activities Operating systems perform basic tasks, such as recognizing input from the keyboard, sending output to the monitor, keeping track of files and folders on storage devices, and controlling peripheral devices, such as disk drives and printers. An operating system must also ensure that different programs and users working at the same time do not interfere with each other. In addition, the OS is responsible for security, ensuring that unauthorized users and programs do not access the system.

1.4.2 Allocating and Assigning System Resources The operating system is responsible for determining what computer resources a program needs (such as CPU time, memory space, disks, input and output devices) and for allocating and assigning them to run the program.

Key Point

1.5 The History of Python 13

1.4.3 Scheduling Operations The OS is responsible for scheduling programs’ activities to make efficient use of system resources. Many of today’s operating systems support such techniques as multiprogramming, multithreading, and multiprocessing to increase system performance.

Multiprogramming allows multiple programs to run simultaneously by sharing the same CPU. The CPU is much faster than the computer’s other components. As a result, it is idle most of the time—for example, while waiting for data to be transferred from a disk or waiting for other system resources to respond. A multiprogramming OS takes advantage of this situa- tion by allowing multiple programs to use the CPU when it would otherwise be idle. For example, multiprogramming enables you to use a word processor to edit a file at the same time as your Web browser is downloading a file.

Multithreading allows a single program to execute multiple tasks at the same time. For instance, a word-processing program allows users to simultaneously edit text and save it to a disk. In this example, editing and saving are two tasks within the same application. These two tasks may run concurrently.

Multiprocessing, or parallel processing, uses two or more processors together to per- form subtasks concurrently and then combine solutions of the subtasks to obtain a solution for the entire task. It is like a surgical operation where several doctors work together on one patient.

1.18 What is an operating system? List some popular operating systems. 1.19 What are the major responsibilities of an operating system? 1.20 What are multiprogramming, multithreading, and multiprocessing?

1.5 The History of Python Python is a general-purpose, interpreted, object-oriented programming language.

Python was created by Guido van Rossum in the Netherlands in 1990 and was named after the popular British comedy troupe Monty Python’s Flying Circus. Van Rossum developed Python as a hobby, and Python has become a popular programming language widely used in industry and academia due to its simple, concise, and intuitive syntax and extensive library.

Python is a general-purpose programming language. That means you can use Python to write code for any programming task. Python is now used in the Google search engine, in mission-critical projects at NASA, and in transaction processing at the New York Stock Exchange.

Python is interpreted, which means that Python code is translated and executed by an inter- preter, one statement at a time, as described earlier in the chapter.

Python is an object-oriented programming (OOP) language. Data in Python are objects created from classes. A class is essentially a type or category that defines objects of the same kind with properties and methods for manipulating objects. Object-oriented programming is a powerful tool for developing reusable software. Object-oriented programming in Python will be covered in detail starting in Chapter 7.

Python is now being developed and maintained by a large team of volunteers and is avail- able for free from the Python Software Foundation. Two versions of Python are currently coexistent: Python 2 and Python 3. The programs written in Python 3 will not run in Python 2. Python 3 is a newer version, but it is not backward-compatible with Python 2. This means that if you write a program using the Python 2 syntax, it may not work with a Python 3 inter- preter. Python provides a tool that automatically converts code written in Python 2 into syntax Python 3 can use. Python 2 will eventually be replaced by Python 3. This book teaches pro- gramming using Python 3.

multiprogramming

multithreading

multiprocessing

general-purpose programming language

interpreted

object-oriented programming (OOP)

Python 2 vs. Python 3

✓Point✓Check

Key Point

14 Chapter 1 Introduction to Computers, Programs, and Python

1.21 Python is interpreted. What does that mean? 1.22 Can a program written in Python 2 run in Python 3? 1.23 Can a program written using Python 3 run in Python 2?

1.6 Getting Started with Python A Python program is executed from the Python interpreter.

Let’s get started by writing a simple Python program that displays the messages Welcome to Python and Python is fun on the console. The word console is an old computer term that refers to the text entry and display device of a computer. Console input means to receive input from the keyboard and console output means to display output to the monitor.

Note You can run Python on the Windows, UNIX, and Mac operating systems. For informa- tion on installing Python, see Supplement I.B, Installing and Using Python, on the Companion Website.

1.6.1 Launching Python Assume you have Python installed on the Windows OS. You can start Python in a com- mand window by typing python at the command prompt, as shown in Figure 1.11, or by using IDLE, as shown in Figure 1.12. IDLE (Interactive DeveLopment Environment) is an integrated development environment (IDE) for Python. You can create, open, save, edit, and run Python programs in IDLE. Both the command-line Python interpreter and IDLE are available after Python is installed on your machine. Note that Python (command line)

console

install Python

IDLE

FIGURE 1.11 You can launch Python from the command window.

FIGURE 1.12 You can use Python from IDLE.

Key Point

console input

console output

✓Point✓Check

VideoNote Start with Python

1.6 Getting Started with Python 15

and IDLE can also be accessed directly from the Windows Start button by searching for Python (command line) or IDLE (Python GUI) on Windows 7 or Vista, as shown in Figure 1.13.

After Python starts, you will see the symbol >>>. This is the Python statement prompt, and it is where you can enter a Python statement.

Note Type the commands exactly as they are written in this text. Formatting and other rules will be discussed later in this chapter.

Now, type print("Welcome to Python") and press the Enter key. The string Welcome to Python appears on the console, as shown in Figure 1.11. String is a programming term meaning a sequence of characters.

Note Note that Python requires double or single quotation marks around strings to delineate them from other code. As you can see in the output, Python doesn’t display those quotation marks.

The print statement is one of Python’s built-in functions that can be used to display a string on the console. A function performs actions. In the case of the print function, it dis- plays a message to the console.

Note In programming terminology, when you use a function, you are said to be “invoking a function” or “calling a function.”

Next, type print("Python is fun") and press the Enter key. The string Python is fun appears on the console, as shown in Figure 1.11. You can enter additional statements at the statement prompt >>>.

Note To exit Python, press CTRL+Z and then the Enter key.

Python IDLE Python command line

Enter Python here

FIGURE 1.13 You can launch the Python IDLE and command line from the Start button.

Python statement prompt >>>

string

function

invoking a function

calling a function

16 Chapter 1 Introduction to Computers, Programs, and Python

1.6.2 Creating Python Source Code Files Entering Python statements at the statement prompt >>> is convenient, but the statements are not saved. To save statements for later use, you can create a text file to store the statements and use the following command to execute the statements in the file:

python filename.py

The text file can be created using a text editor such as Notepad. The text file, filename, is called a Python source file or script file, or module. By convention, Python files are named with the extension .py.

Running a Python program from a script file is known as running Python in script mode. Typing a statement at the statement prompt >>> and executing it is called running Python in interactive mode.

Note Besides developing and running Python programs from the command window, you can create, save, modify, and run a Python script from IDLE. For information on using IDLE, see Supplement I.C on the Companion Website. Your instructor may also ask you to use Eclipse. Eclipse is a popular interactive development environment (IDE) used to develop programs quickly. Editing, running, debugging, and online help are integrated in one graphical user interface. If you want to develop Python programs using Eclipse, see Supplement I.D, on the Companion Website.

Listing 1.1 shows you a Python program that displays the messages Welcome to Python and Python is fun.

LISTING 1.1 Welcome.py 1 # Display two messages 2 print("Welcome to Python") 3 print("Python is fun")

In this text, line numbers are displayed for reference purposes; they are not part of the pro- gram. So, don’t type line numbers in your program.

Suppose the statements are saved in a file named Welcome.py. To run the program, enter python Welcome.py at the command prompt, as shown in Figure 1.14.

source file script file module .py file script mode interactive mode

Python on Eclipse

comment print a message

FIGURE 1.14 You can run a Python script file from a command window.

In Listing 1.1, line 1 is a comment that documents what the program is and how it is con- structed. Comments help programmers communicate and understand a program. They are not programming statements and thus are ignored by the interpreter. In Python, comments are preceded by a pound sign (#) on a line, called a line comment, or enclosed between three con- secutive single quotation marks (''') on one or several lines, called a paragraph comment.

line numbers

execute the program

comment

line comment

paragraph comment

1.6 Getting Started with Python 17

When the Python interpreter sees #, it ignores all text after # on the same line. When it sees ''', it scans for the next ''' and ignores any text between the triple quotation marks. Here are examples of comments:

# This program displays Welcome to Python

''' This program displays Welcome to Python and Python is fun

'''

Indentation matters in Python. Note that the statements are entered from the first column in the new line. The Python interpreter will report an error if the program is typed as follows:

# Display two messages print("Welcome to Python")

print("Python is fun")

Don’t put any punctuation at the end of a statement. For example, the Python interpreter will report errors for the following code:

# Display two messages print("Welcome to Python"). print("Python is fun"),

Python programs are case sensitive. It would be wrong, for example, to replace print in the program with Print.

You have seen several special characters (#, ", ()) in the program. They are used in almost every program. Table 1.2 summarizes their uses.

TABLE 1.2 Special Characters

Character Name Description

() Opening and closing parentheses Used with functions.

# Pound sign Precedes a comment line.

" " Opening and closing quotation marks Encloses a string (i.e., sequence of characters).

''' ''' Paragraph comments Encloses a paragraph comment.

The program in Listing 1.1 displays two messages. Once you understand the program, it is easy to extend it to display more messages. For example, you can rewrite the program to dis- play three messages, as shown in Listing 1.2.

LISTING 1.2 WelcomeWithThreeMessages.py 1 # Display three messages 2 print("Welcome to Python") 3 print("Python is fun") 4 print("Problem Driven")

Welcome to Python Python is fun Problem Driven

indentation

case sensitive

special characters

comment print statement

BAD CO

DE

BAD CO

DE

18 Chapter 1 Introduction to Computers, Programs, and Python

1.6.3 Using Python to Perform Mathematical Computations Python programs can perform all sorts of mathematical computations and display the result. To display the addition, subtraction, multiplication, and division of two numbers, x and y, use the following code:

print(x + y) print(x – y) print(x * y) print(x / y)

Listing 1.3 shows an example of a program that evaluates and prints its result.

LISTING 1.3 ComputeExpression.py 1 # Compute expression 2 print((10.5 + 2 * 3) / (45 – 3.5))

10.5 + 2 * 3 45 - 3.5

comment compute expression

0.397590361446

As you can see, it is a straightforward process to translate an arithmetic expression to a Python expression. We will discuss Python expressions further in Chapter 2.

1.24 You can run Python in two modes. Explain these two modes. 1.25 Is Python case sensitive? 1.26 What is the Python source filename extension by convention? 1.27 What is the command to run a Python source file? 1.28 What is a comment? How do you denote a comment line and a comment paragraph? 1.29 What is the statement to display the message Hello world on the console? 1.30 Identify and fix the errors in the following code:

1 # Display two messages 2 print("Welcome to Python") 3 print("Python is fun").

1.31 Show the output of the following code: print("3.5 * 4 / 2 - 2.5 is") print(3.5 * 4 / 2 - 2.5)

1.7 Programming Style and Documentation Good programming style and proper documentation make a program easy to read and prevents errors.

Programming style deals with what programs look like. When you create programs with a professional programming style, they not only execute properly but are easy for people to read and understand. This is very important if other programmers will access or modify your programs.

Documentation is the body of explanatory remarks and comments pertaining to a program. These remarks and comments explain various parts of the program and help others understand its structure and function. As you saw earlier in the chapter, remarks and comments are

programming style

documentation

✓Point✓Check

Key Point

1.8 Programming Errors 19

embedded within the program itself; Python’s interpreter simply ignores them when the pro- gram is executed.

Programming style and documentation are as important as coding. Here are a few guidelines.

1.7.1 Appropriate Comments and Comment Styles Include a summary comment at the beginning of the program to explain what the program does, its key features, and any unique techniques it uses. In a long program, you should also include comments that introduce each major step and explain anything that is difficult to read. It is important to make comments concise so that they do not crowd the program or make it difficult to read.

1.7.2 Proper Spacing A consistent spacing style makes programs clear and easy to read, debug (find and fix errors), and maintain.

A single space should be added on both sides of an operator, as shown in the following statement:

More detailed guidelines can be found in Supplement I.F, Python Coding Style Guidelines, on the Companion Website.

1.8 Programming Errors Programming errors can be categorized into three types: syntax errors, runtime errors, and logic errors.

1.8.1 Syntax Errors The most common error you will encounter are syntax errors. Like any programming lan- guage, Python has its own syntax, and you need to write code that obeys the syntax rules. If your program violates the rules—for example, if a quotation mark is missing or a word is misspelled—Python will report syntax errors.

Syntax errors result from errors in code construction, such as mistyping a statement, incor- rect indentation, omitting some necessary punctuation, or using an opening parenthesis with- out a corresponding closing parenthesis. These errors are usually easy to detect, because Python tells you where they are and what caused them. For example, the following print statement has a syntax error:

common errors

syntax rules

syntax errors

print(3+4*4) Bad style

print(3 + 4 * 4) Good style

Key Point

20 Chapter 1 Introduction to Computers, Programs, and Python

The string Programming is fun should be closed with a closing quotation mark.

Tip If you don’t know how to correct a syntax error, compare your program closely, charac- ter by character, with similar examples in the text. In the first few weeks of this course, you will probably spend a lot of time fixing syntax errors. Soon, you will be familiar with Python syntax and will be able to fix syntax errors quickly.

1.8.2 Runtime Errors Runtime errors are errors that cause a program to terminate abnormally. They occur while a program is running if the Python interpreter detects an operation that is impossible to carry out. Input mistakes typically cause runtime errors. An input error occurs when the user enters a value that the program cannot handle. For instance, if the program expects to read in a number, but instead the user enters a string of text, this causes data-type errors to occur in the program.

Another common source of runtime errors is division by zero. This happens when the divi- sor is zero for integer divisions. For example, the expression 1 / 0 in the following statement would cause a runtime error.

logic errors

Fahrenheit 35 is Celsius degree -12.555555555555554

You will get Celsius –12.55 degrees, which is wrong. It should be 1.66. To get the correct result, you need to use 5 / 9 * (35 – 32) rather than 5 / 9 * 35 – 32 in the expression. That is, you need to add parentheses around (35 – 32) so Python will calculate that expression first before doing the division.

In Python, syntax errors are actually treated like runtime errors because they are detected by the interpreter when the program is executed. In general, syntax and runtime errors are easy to find and easy to correct, because Python gives indications as to where the errors came from and why they are wrong. Finding logic errors, on the other hand, can be very challenging.

fix syntax errors

runtime errors

input errors

1.8.3 Logic Errors Logic errors occur when a program does not perform the way it was intended to. Errors of this kind occur for many different reasons. For example, suppose you wrote the program in Listing 1.4 to convert a temperature (35 degrees) from Fahrenheit to Celsius.

LISTING 1.4 ShowLogicErrors.py 1 # Convert Fahrenheit to Celsius 2 print("Fahrenheit 35 is Celsius degree ") 3 print(5 / 9 * 35 - 32)

1.9 Getting Started with Graphics Programming 21

turtle

Tkinter

1.32 What are three kinds of program errors? 1.33 If you forget to put a closing quotation mark on a string, what kind of error will be

raised?

1.34 If your program needs to read data from a file, but the file does not exist, an error would occur when running this program. What kind of error is this?

1.35 Suppose you write a program for computing the perimeter of a rectangle and you mistakenly write your program so that it computes the area of a rectangle. What kind of error is this?

1.9 Getting Started with Graphics Programming Turtle is Python’s built-in graphics module for drawing lines, circles, and other shapes, including text. It is easy to learn and simple to use.

Beginners often enjoy learning programming by using graphics. For this reason, we provide a section on graphics programming at the end of most of the chapters in the first part of the book. However, these materials are not mandatory. They can be skipped or covered later.

There are many ways to write graphics programs in Python. A simple way to start graphics programming is to use Python’s built-in turtle module. Later in the book, we will introduce Tkinter for developing comprehensive graphical user interface applications.

1.9.1 Drawing and Adding Color to a Figure The following procedure will give you a basic introduction to using the turtle module. Sub- sequent chapters introduce more features.

1. Launch Python by choosing Python (command line) from the Windows Start button or by typing python at the command prompt.

2. At the Python statement prompt >>>, type the following command to import the turtle module. This command imports all functions defined in the turtle module and makes them available for you to use.

>>> import turtle # Import turtle module

3. Type the following command to show the current location and direction of the turtle, as shown in Figure 1.15a.

>>> turtle.showturtle()

Graphics programming using the Python Turtle module is like drawing with a pen. The arrowhead indicates the current position and direction of the pen. turtle is initially positioned at the center of the window. Here, turtle refers to the object for drawing graphics (objects will be introduced in Chapter 3).

4. Type the following command to draw a text string:

>>> turtle.write("Welcome to Python")

Your window should look like the one shown in Figure 1.15b.

5. Type the following command to move the arrowhead 100 pixels forward to draw a line in the direction the arrow is pointing:

>>> turtle.forward(100)

Your window should now look like the one shown in Figure 1.15c.

To draw the rest of Figure 1.15, continue with these steps.

VideoNote

Start with Turtle graphics

Key Point

✓Point✓Check

22 Chapter 1 Introduction to Computers, Programs, and Python

6. Type the following commands to turn the arrowhead right 90 degrees, change the turtle’s color to red, and move the arrowhead 50 pixels forward to draw a line, as shown in Figure 1.15d:

>>> turtle.right(90) >>> turtle.color("red") >>> turtle.forward(50)

7. Now, type the following commands to turn the arrowhead right 90 degrees, set the color to green, and move the arrowhead 100 pixels forward to draw a line, as shown in Figure 1.15e:

>>> turtle.right(90) >>> turtle.color("green") >>> turtle.forward(100)

8. Finally, type the following commands to turn the arrowhead right 45 degrees and move it 80 pixels forward to draw a line, as shown in Figure 1.15f:

>>> turtle.right(45) >>> turtle.forward(80)

9. You can now close the Turtle Graphics window and exit Python.

1.9.2 Moving the Pen to Any Location When the Turtle program starts, the arrowhead is at the center of the Python Turtle Graphics window at the coordinates (0, 0), as shown in Figure 1.16a. You can also use the goto(x, y) command to move the turtle to any specified point (x, y).

Restart Python and type the following command to move the pen to (0, 50) from (0, 0), as shown in Figure 1.16b.

>>> import turtle >>> turtle.goto(0, 50)

(a) (b)

(d) (e) (f)

(c)

FIGURE 1.15 Graphics are dynamically displayed with each statement.

1.9 Getting Started with Graphics Programming 23

(a) (b)

(d) (e)

(c) (0, 0)

(0, 50)

(50, –50)

Y-axis

X-axis(0, 0)

FIGURE 1.16 (a) The center of the Turtle Graphics window is at the coordinates (0, 0). (b) Move to (0, 50). (c) Move the pen to (50, –50). (d) Set color to red. (e) Draw a circle using the circle command.

You can also lift the pen up or put it down to control whether to draw a line when the pen is moved by using the penup() and pendown() commands. For example, the following commands move the pen to (50, -50), as shown in Figure 1.16c.

>>> turtle.penup() >>> turtle.goto(50, -50) >>> turtle.pendown()

You can draw a circle using the circle command. For example, the following commands set color red (Figure 1.16d) and draw a circle with radius 50 (Figure 1.16e).

>>> turtle.color("red") >>> turtle.circle(50) # Draw a circle with radius 50

1.9.3 Drawing the Olympic Rings Logo Listing 1.5 shows a program for drawing the Olympics rings logo, as shown in Figure 1.17.

LISTING 1.5 OlympicSymbol.py 1 import turtle 2 3 turtle.color("blue") 4 turtle.penup() 5 turtle.goto(-110, -25) 6 turtle.pendown() 7 turtle.circle(45) 8 9 turtle.color("black")

draw blue circle

draw black circle

24 Chapter 1 Introduction to Computers, Programs, and Python

10 turtle.penup() 11 turtle.goto(0, -25) 12 turtle.pendown() 13 turtle.circle(45) 14 15 turtle.color("red") 16 turtle.penup() 17 turtle.goto(110, -25) 18 turtle.pendown() 19 turtle.circle(45) 20 21 turtle.color("yellow") 22 turtle.penup() 23 turtle.goto(-55, -75) 24 turtle.pendown() 25 turtle.circle(45) 26 27 turtle.color("green") 28 turtle.penup() 29 turtle.goto(55, -75) 30 turtle.pendown() 31 turtle.circle(45) 32 33 turtle.done()

The program imports the turtle module to use the Turtle Graphics window (line 1). It moves the pen to (line 5) and draws a blue circle with radius 45 (line 7). Similarly, it draws a black circle (lines 9–13), a red circle (lines 15–19), a yellow circle (lines 21–25), and a green circle (lines 27–31).

Line 33 invokes turtle’s done() command, which causes the program to pause until the user closes the Python Turtle Graphics window. The purpose of this is to give the user time to view the graphics. Without this line, the graphics window would be closed right after the pro- gram is finished.

1.36 How do you import the turtle module? 1.37 How do you display text in Turtle? 1.38 How do you move the pen forward? 1.39 How do you set a new color? 1.40 How do you move the pen without drawing anything? 1.41 How do you draw a circle? 1.42 What is the purpose of turtle.done() in line 33 in Listing 1.5?

(-110, -25)

FIGURE 1.17 The program draws the Olympics rings logo.

draw yellow circle

draw green circle

pause

✓Point✓Check

draw red circle

Chapter Summary 25

KEY TERMS

.py file 16 assembler 10 assembly language 10 bit 4 bus 2 byte 4 cable modem 8 calling a function 15 central processing unit (CPU) 3 comment 16 compiler 10 console 14 dot pitch 8 DSL (digital subscriber line) 8 encoding scheme 4 function 15 hardware 2 high-level language 10 IDLE (Interactive DeveLopment

Environment) 14 indentation 17 interactive mode 16 interpreter 10 invoking a function 15

line comment 16 logic error 20 low-level language 10 machine language 9 memory 5 modem 8 module 16 motherboard 3 network interface card (NIC) 8 operating system (OS) 12 pixel 8 program 2 runtime errors 20 screen resolution 8 script file 16 script mode 16 software 2 source code 10 source file 16 source program 10 statement 10 storage device 5 syntax errors 19 syntax rules 19

Note The above terms are defined in the present chapter. Supplement I.A, Glossary, lists all the key terms and descriptions in the book, organized by chapters.

CHAPTER SUMMARY 1. A computer is an electronic device that stores and processes data.

2. A computer includes both hardware and software.

3. Hardware is the physical aspect of the computer that can be touched.

4. Computer programs, known as software, are the invisible instructions that control the hardware and make it perform tasks.

5. Computer programming is the writing of instructions (i.e., code) for computers to perform.

6. The central processing unit (CPU) is a computer’s brain. It retrieves instructions from memory and executes them.

7. Computers use zeros and ones because digital devices have two stable electrical states, off and on, referred to by convention as zero and one.

8. A bit is a binary digit 0 or 1.

Supplement I.A

26 Chapter 1 Introduction to Computers, Programs, and Python

9. A byte is a sequence of 8 bits.

10. A kilobyte is about 1,000 bytes, a megabyte about 1 million bytes, a gigabyte about 1 billion bytes, and a terabyte about 1,000 gigabytes.

11. Memory stores data and program instructions for the CPU to execute.

12. A memory unit is an ordered sequence of bytes.

13. Memory is volatile, because information that hasn’t been saved is lost when the power is turned off.

14. Programs and data are permanently stored on storage devices and are moved to memory when the computer actually uses them.

15. The machine language is a set of primitive instructions built into every computer.

16. Assembly language is a low-level programming language in which a mnemonic is used to represent each machine-language instruction.

17. High-level languages are English-like and easy to learn and program.

18. A program written in a high-level language is called source code.

19. A compiler is a software program that translates the source program into a machine- language program.

20. The operating system (OS) is a program that manages and controls a computer’s activities.

21. You can run Python on Windows, UNIX, and Mac.

22. Python is interpreted, meaning that Python translates each statement and processes it one at a time.

23. You can enter Python statements interactively from the Python statement prompt >>> or store all your code in one file and execute it using one command.

24. To run a Python source file from the command line, use the python filename.py command.

25. In Python, comments are preceded by a pound sign (#) on a line, called a line comment, or enclosed between triple quotation marks (''' and ''') on one or several lines, called a paragraph comment.