4.26 lab brute force equation solver

Python Programming Problems

ONLINE ACCESS

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.