Top
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
6 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
