Preface iii

Special Features xviii

1 Introduction 1

1.1 Computer Programs 2

1.2 The Anatomy of a Computer 3

CS 1 Computers Are Everywhere 5

1.3 The Python Programming Language 5

1.4 Becoming Familiar with Your Programming Environment 6

PT 1 Interactive Mode 8

PT 2 Backup Copies 9

ST 1 The Python Interpreter 10

1.5 Analyzing Your First Program 11

1.6 Errors 13

CE 1 Misspelling Words 14

1.7 PROBLEM SOLVING: Algorithm Design 15

CS 2 Data Is Everywhere 17

HT 1 Describing an Algorithm with Pseudocode 18

WE 1 Writing an Algorithm for Tiling a Floor 20

2 Programming With Numbers and Strings 23

2.1 Variables 24

Defining Variables 24

Number Types 26

Variable Names 27

Constants 28

Comments 29

CE 1 Using Undefined Variables 30

PT 1 Choose Descriptive Variable Names 30

PT 2 Do Not Use Magic Numbers 30

2.2 Arithmetic 31

Basic Arithmetic Operations 31

Powers 32

Floor Division and Remainder 32

Calling Functions 33

Mathematical Functions 35

CE 2 Roundoff Errors 36

CE 3 Unbalanced Parentheses 37

PT 3 Use Spaces in Expressions 37

ST 1 Other Ways to Import Modules 38

ST 2 Combining Assignment and Arithmetic 38

ST 3 Line Joining 38

2.3 PROBLEM SOLVING: First Do It By Hand 39

WE 1 Computing Travel Time 40

2.4 Strings 41

The String Type 41

Concatenation and Repetition 42

Converting Between Numbers and Strings 43

Strings and Characters 44

String Methods 45

ST 4 Character Values 46

ST 5 Escape Sequences 47

CS 1 International Alphabets and Unicode 47

2.5 Input and Output 48

User Input 48

Numerical Input 49

Formatted Output 50

PT 4 Don’t Wait to Convert 53

HT 1 Writing Simple Programs 53

WE 2 Computing the Cost of Stamps 56

CS 2 Bugs in Silicon 58

2.6 GRAPHICS: Simple Drawings 58

Creating a Window 59

Lines and Polygons 60

Filled Shapes and Color 62

Ovals, Circles, and Text 64

HT 2 GRAPHICS: Drawing Graphical Shapes 65

TOOLBOX 1 Symbolic Processing with SymPy 68

3 Decisions 73

3.1 The if Statement 74

CE 1 Tabs 77

PT 1 Avoid Duplication in Branches 78

ST 1 Conditional Expressions 78

3.2 Relational Operators 79

CE 2 Exact Comparison of Floating-Point Numbers 82

ST 2 Lexicographic Ordering of Strings 82

HT 1 Implementing an if Statement 83

WE 1 Extracting the Middle 85

3.3 Nested Branches 87

PT 2 Hand-Tracing 89

CS 1 Dysfunctional Computerized Systems 90

3.4 Multiple Alternatives 91

TOOLBOX 1 Sending E-mail 93

3.5 PROBLEM SOLVING: Flowcharts 96

3.6 PROBLEM SOLVING: Test Cases 99

PT 3 Make a Schedule and Make Time for Unexpected Problems 100

3.7 Boolean Variables and Operators 101

CE 3 Confusing and and or Conditions 104

PT 4 Readability 104

ST 3 Chaining Relational Operators 105

ST 4 Short-Circuit Evaluation of Boolean Operators 105

ST 5 De Morgan’s Law 106

3.8 Analyzing Strings 106

3.9 APPLICATION: Input Validation 110

ST 6 Terminating a Program 112

ST 7 Interactive Graphical Programs 112

CS 2 Artificial Intelligence 113

WE 2 GRAPHICS: Intersecting Circles 113

TOOLBOX 2 Plotting Simple Graphs 117

4 Loops 125

4.1 The while Loop 126

CE 1 Don’t Think “Are We There Yet?” 130

CE 2 Infinite Loops 130

CE 3 Off-by-One Errors 131

ST 1 Special Form of the print Function 132

CS 1 The First Bug 132

4.2 PROBLEM SOLVING: Hand-Tracing 133

4.3 APPLICATION: Processing Sentinel Values 135

ST 2 Processing Sentinel Values with a Boolean Variable 138

ST 3 Redirection of Input and Output 138

4.4 PROBLEM SOLVING: Storyboards 139

4.5 Common Loop Algorithms 141

Sum and Average Value 141

Counting Matches 142

Prompting Until a Match is Found 142

Maximum and Minimum 142

Comparing Adjacent Values 143

4.6 The for Loop 145

PT 1 Count Iterations 148

HT 1 Writing a Loop 149

4.7 Nested Loops 152

WE 1 Average Exam Grades 155

WE 2 A Grade Distribution Histogram 157

4.8 Processing Strings 159

Counting Matches 159

Finding All Matches 160

Finding the First or Last Match 160

Validating a String 161

Building a New String 162

4.9 APPLICATION: Random Numbers and Simulations 164

Generating Random Numbers 164

Simulating Die Tosses 165

The Monte Carlo Method 165

WE 3 GRAPHICS: Bull’s Eye 167

4.10 GRAPHICS: Digital Image Processing 169

Filtering Images 170

Reconfiguring Images 172

4.11 PROBLEM SOLVING: Solve a Simpler Problem First 174

CS 2 Digital Piracy 180

5 Functions 183

5.1 Functions as Black Boxes 184

5.2 Implementing and Testing Functions 185

Implementing a Function 186

Testing a Function 186

Programs that Contain Functions 187

PT 1 Function Comments 189

PT 2 Naming Functions 190

5.3 Parameter Passing 190

PT 3 Do Not Modify Parameter Variables 191

CE 1 Trying to Modify Arguments 192

5.4 Return Values 192

ST 1 Using Single-Line Compound Statements 193

HT 1 Implementing a Function 194

WE 1 Generating Random Passwords 196

5.5 Functions Without Return Values 201

CS 1 Personal Computing 202

5.6 PROBLEM SOLVING: Reusable Functions 203

5.7 PROBLEM SOLVING: Stepwise Refinement 205

PT 4 Keep Functions Short 209

PT 5 Tracing Functions 210

PT 6 Stubs 211

WE 2 Calculating a Course Grade 211

WE 3 Using a Debugger 214

5.8 Variable Scope 219

PT 7 Avoid Global Variables 221

WE 4 GRAPHICS: Rolling Dice 221

5.9 GRAPHICS: Building an Image Processing Toolkit 224

Getting Started 224

Comparing Images 225

Adjusting Image Brightness 226

Rotating an Image 227

Using the Toolkit 228

WE 5 Plotting Growth or Decay 230

5.10 Recursive Functions (Optional) 232

HT 2 Thinking Recursively 234

TOOLBOX 1 Turtle Graphics 236

LISTS 245

6.1 Basic Properties of Lists 246

Creating Lists 246

Accessing List Elements 247

Traversing Lists 248

List References 249

CE 1 Out-of-Range Errors 250

PT 1 Use Lists for Sequences of Related Items 250

ST 1 Negative Subscripts 250

ST 2 Common Container Functions 251

CS 1 Computer Viruses 251

6.2 List Operations 252

Appending Elements 252

Inserting an Element 253

Finding an Element 254

Removing an Element 254

Concatenation and Replication 255

Equality Testing 256

Sum, Maximum, Minimum, and Sorting 256

Copying Lists 256

ST 3 Slices 258

6.3 Common List Algorithms 259

Filling 259

Combining List Elements 259

Element Separators 260

Maximum and Minimum 260

Linear Search 261

Collecting and Counting Matches 261

Removing Matches 262

Swapping Elements 263

Reading Input 264

WE 1 Plotting Trigonometric Functions 265

6.4 Using Lists with Functions 268

ST 4 Call by Value and Call by Reference 271

ST 5 Tuples 271

ST 6 Functions with a Variable Number of Arguments 272

ST 7 Tuple Assignment 272

ST 8 Returning Multiple Values with Tuples 273

TOOLBOX 1 Editing Sound Files 273

6.5 PROBLEM SOLVING: Adapting Algorithms 275

HT 1 Working with Lists 276

WE 2 Rolling the Dice 278

6.6 PROBLEM SOLVING: Discovering Algorithms by Manipulating Physical Objects 282

6.7 Tables 285

Creating Tables 286

Accessing Elements 287

Locating Neighboring Elements 287

Computing Row and Column Totals 288

Using Tables with Functions 289

WE 3 A World Population Table 290

ST 9 Tables with Variable Row Lengths 292

WE 4 GRAPHICS: Drawing Regular Polygons 293

7 Files and Exceptions 299

7.1 Reading and Writing Text Files 300

Opening a File 300

Reading from a File 301

Writing from a File 302

A File Processing Example 302

CE 1 Backslashes in File Names 303

7.2 Text Input and Output 304

Iterating over the Lines of a File 304

Reading Words 306

Reading Characters 308

Reading Records 309

ST 1 Reading the Entire File 312

ST 2 Regular Expressions 312

ST 3 Character Encodings 313

TOOLBOX 1 Working with CSV Files 314

7.3 Command Line Arguments 316

HT 1 Processing Text Files 319

WE 1 Analyzing Baby Names 322

TOOLBOX 2 Working with Files and Directories 325

CS 1 Encryption Algorithms 327

7.4 Binary Files and Random Access (Optional) 328

Reading and Writing Binary Files 328

Random Access 329

Image Files 330

Processing BMP Files 331

WE 2 GRAPHICS: Displaying a Scene File 334

7.5 Exception Handling 337

Raising Exceptions 338

Handling Exceptions 339

The finally Clause 341

PT 1 Raise Early, Handle Late 342

PT 2 Do Not Use except and finally in the Same try Statement 342

ST 4 The with Statement 343

TOOLBOX 3 Reading Web Pages 343

7.6 APPLICATION: Handling Input Errors 344

TOOLBOX 4 Statistical Analysis 348

WE 3 Creating a Bubble Chart 352

CS 2 The Ariane Rocket Incident 355

8 Sets and Dictionaries 357

8.1 Sets 358

Creating and Using Sets 358

Adding and Removing Elements 359

Subsets 360

Set Union, Intersection, and Difference 361

WE 1 Counting Unique Words 364

PT 1 Use Python Sets, Not Lists, for Efficient Set

Operations 366

ST 1 Hashing 367

CS 1 Standardization 368

8.2 Dictionaries 368

Creating Dictionaries 369

Accessing Dictionary Values 370

Adding and Modifying Items 370

Removing Items 371

Traversing a Dictionary 372

ST 2 Iterating over Dictionary Items 374

ST 3 Storing Data Records 375

WE 2 Translating Text Messages 375

8.3 Complex Structures 378

A Dictionary of Sets 378

A Dictionary of Lists 381

ST 4 User Modules 383

WE 3 GRAPHICS: Pie Charts 384

TOOLBOX 1 Harvesting JSON Data from the Web 388

9 Objects and Classes 393

9.1 Object-Oriented Programming 394

9.2 Implementing a Simple Class 396

9.3 Specifying the Public Interface of a Class 399

9.4 Designing the Data Representation 401

PT 1 Make All Instance Variables Private, Most Methods Public 402

9.5 Constructors 402

CE 1 Trying to Call a Constructor 404

ST 1 Default and Named Arguments 404

9.6 Implementing Methods 405

PT 2 Define Instance Variables Only in the Constructor 407

ST 2 Class Variables 408

9.7 Testing a Class 409

HT 1 Implementing a Class 410

WE 1 Implementing a Bank Account Class 414

9.8 PROBLEM SOLVING: Tracing Objects 416

9.9 PROBLEM SOLVING: Patterns for Object Data 419

Keeping a Total 419

Counting Events 420

Collecting Values 420

Managing Properties of an Object 421

Modeling Objects with Distinct States 421

Describing the Position of an Object 422

9.10 Object References 423

Shared References 424

The None Reference 425

The self Reference 426

The Lifetime of Objects 426

CS 1 Electronic Voting 427

9.11 APPLICATION: Writing a Fraction Class 428

Fraction Class Design 428

The Constructor 429

Special Methods 430

Arithmetic Operations 432

Logical Operations 433

ST 3 Object Types and Instances 435

WE 2 GRAPHICS: A Die Class 436

CS 2 Open Source and Free Software 439

10 Inheritance 443

10.1 Inheritance Hierarchies 444

PT 1 Use a Single Class for Variation in Values, Inheritance for Variation in Behavior 447

ST 1 The Cosmic Superclass: object 447

10.2 Implementing Subclasses 449

CE 1 Confusing Super- and Subclasses 451

10.3 Calling the Superclass Constructor 452

10.4 Overriding Methods 455

CE 2 Forgetting to Use the super Function When Invoking a Superclass Method 458

10.5 Polymorphism 458

ST 2 Subclasses and Instances 461

ST 3 Dynamic Method Lookup 461

ST 4 Abstract Classes 462

CE 3 Don’t Use Type Tests 463

HT 1 Developing an Inheritance Hierarchy 463

WE 1 Implementing an Employee Hierarchy for Payroll Processing 468

10.6 APPLICATION: A Geometric Shape Class Hierarchy 472

The Base Class 472

Basic Shapes 474

Groups of Shapes 477

TOOLBOX 1 Game Programming 480

11 Recursion 489

11.1 Triangle Numbers Revisited 490

CE 1 Infinite Recursion 493

ST 1 Recursion with Objects 493

11.2 PROBLEM SOLVING: Thinking Recursively 494

WE 1 Finding Files 497

11.3 Recursive Helper Functions 498

11.4 The Efficiency of Recursion 499

11.5 Permutations 504

CS 1 The Limits of Computation 506

11.6 Backtracking 508

WE 2 Towers of Hanoi 512

11.7 Mutual Recursion 515

TOOLBOX 1 Analyzing Web Pages with Beautiful Soup 519

12 Sorting and Searching 525

12.1 Selection Sort 526

12.2 Profiling the Selection Sort Algorithm 528

12.3 Analyzing the Performance of the Selection Sort Algorithm 530

ST 1 Oh, Omega, and Theta 531

ST 2 Insertion Sort 532

12.4 Merge Sort 534

12.5 Analyzing the Merge Sort Algorithm 536

ST 3 The Quicksort Algorithm 538

CS 1 The First Programmer 540

12.6 Searching 541

Linear Search 541

Binary Search 542

12.7 PROBLEM SOLVING: Estimating the Running Time of an Algorithm 544

Linear Time 545

Quadratic Time 546

The Triangle Pattern 547

Logarithmic Time 548

PT 1 Searching and Sorting 549

ST 4 Comparing Objects 549

WE 1 Enhancing the Insertion Sort Algorithm 549

Appendix A Python Operator Summary A-1

Appendix B Python Reserved Word Summary A-3

Appendix C The Python Standard Library A-5

Appendix D The Basic Latin and Latin-1 Subsets of Unicode A-22

Appendix E Binary Numbers and Bit Operations*

Appendix F HTML Summary*

Glossary R-1

Index R-6

Credits R-22

Quick Reference R-23

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.