Preface iii Special Features xviii 1 Introduction 1 1.1 Computer Programs 2 1.2 The Anatomy of a Computer 3 CS1 Computers Are Everywhere 5 1.3 The Python Programming Language 5 1.4 Becoming Familiar with Your Programming Environment 6 PT1 Interactive Mode 8 PT2 Backup Copies 9 ST1 The Python Interpreter 10 1.5 Analyzing Your First Program 11 1.6 Errors 13 CE1 Misspelling Words 14 1.7 PROBLEM SOLVING: Algorithm Design 15 CS2 Data Is Everywhere 17 HT1 Describing an Algorithm with Pseudocode 18 WE1 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 CE1 Using Undefined Variables 30 Pt1 Choose Descriptive Variable Names 30 PT2 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 CE2 Roundoff Errors 36 CE3 Unbalanced Parentheses 37 PT3 Use Spaces in Expressions 37 ST1 Other Ways to Import Modules 38 ST2 Combining Assignment and Arithmetic 38 ST3 Line Joining 38 2.3 PROBLEM SOLVING: First Do It By Hand 39 WE1 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 ST4 Character Values 46 ST5 Escape Sequences 47 CS1 International Alphabets and Unicode 47 2.5 Input and Output 48 User Input 48 Numerical Input 49 Formatted Output 50 PT4 Don’t Wait to Convert 53 HT1 Writing Simple Programs 53 WE2 Computing the Cost of Stamps 56 CS2 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 HT2 GRAPHICS: Drawing Graphical Shapes 65 TOOLBOX 1 Symbolic Processing with SymPy 68 3 Decisions 73 3.1 The if Statement 74 CE1 Tabs 77 PT1 Avoid Duplication in Branches 78 ST1 Conditional Expressions 78 3.2 Relational Operators 79 CE2 Exact Comparison of Floating-Point Numbers 82 ST2 Lexicographic Ordering of Strings 82 HT1 Implementing an if Statement 83 WE1 Extracting the Middle 85 3.3 Nested Branches 87 PT2 Hand-Tracing 89 CS1 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 PT3 Make a Schedule and Make Time for Unexpected Problems 100 3.7 Boolean Variables and Operators 101 CE3 Confusing and and or Conditions 104 PT4 Readability 104 ST3 Chaining Relational Operators 105 ST4 Short-Circuit Evaluation of Boolean Operators 105 ST5 De Morgan’s Law 106 3.8 Analyzing Strings 106 3.9 APPLICATION: Input Validation 110 ST6 Terminating a Program 112 ST7 Interactive Graphical Programs 112 CS2 Artificial Intelligence 113 WE2 GRAPHICS: Intersecting Circles 113 TOOLBOX 2 Plotting Simple Graphs 117 4 Loops 125 4.1 The while Loop 126 CE1 Don’t Think “Are We There Yet?” 130 CE2  Infinite Loops 130 CE3 Off-by-One Errors 131 ST1 Special Form of the print Function 132 CS1 The First Bug 132 4.2 PROBLEM SOLVING: Hand-Tracing 133 4.3 APPLICATION: Processing Sentinel Values 135 ST2 Processing Sentinel Values with a Boolean Variable 138 ST3 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 PT1 Count Iterations 148 HT1 Writing a Loop 149 4.7 Nested Loops 152 WE1 Average Exam Grades 155 WE2 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 WE3 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 CS2 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 PT1 Function Comments 189 PT2 Naming Functions 190 5.3 Parameter Passing 190 PT3 Do Not Modify Parameter Variables 191 CE1 Trying to Modify Arguments 192 5.4 Return Values 192 ST1 Using Single-Line Compound Statements 193 HT1 Implementing a Function 194 WE1 Generating Random Passwords 196 5.5 Functions Without Return Values 201 CS1 Personal Computing 202 5.6 PROBLEM SOLVING: Reusable Functions 203 5.7 PROBLEM SOLVING: Stepwise Refinement 205 PT4 Keep Functions Short 209 PT5 Tracing Functions 210 PT6 Stubs 211 WE2 Calculating a Course Grade 211 WE3 Using a Debugger 214 5.8 Variable Scope 219 PT7 Avoid Global Variables 221 WE4 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 WE5 Plotting Growth or Decay 230 5.10 Recursive Functions (Optional) 232 HT2 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 CE1 Out-of-Range Errors 250 PT1 Use Lists for Sequences of Related Items 250 ST1 Negative Subscripts 250 ST2 Common Container Functions 251 CS1 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 ST3 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 WE1 Plotting Trigonometric Functions 265 6.4 Using Lists with Functions 268 ST4 Call by Value and Call by Reference 271 ST5 Tuples 271 ST6 Functions with a Variable Number of Arguments 272 ST7 Tuple Assignment 272 ST8 Returning Multiple Values with Tuples 273 TOOLBOX 1 Editing Sound Files 273 6.5 PROBLEM SOLVING: Adapting Algorithms 275 HT1 Working with Lists 276 WE2 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 WE3 A World Population Table 290 ST9 Tables with Variable Row Lengths 292 WE4 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 CE1 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 ST1 Reading the Entire File 312 ST2 Regular Expressions 312 ST3 Character Encodings 313 TOOLBOX 1 Working with CSV Files 314 7.3 Command Line Arguments 316 HT1 Processing Text Files 319 WE1 Analyzing Baby Names 322 TOOLBOX 2 Working with Files and Directories 325 CS1 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 WE2 GRAPHICS: Displaying a Scene File 334 7.5 Exception Handling 337 Raising Exceptions 338 Handling Exceptions 339 The finally Clause 341 PT1 Raise Early, Handle Late 342 PT2 Do Not Use except and finally in the Same try Statement 342 ST4 The with Statement 343 TOOLBOX 3 Reading Web Pages 343 7.6 APPLICATION: Handling Input Errors 344 TOOLBOX 4 Statistical Analysis 348 WE3 Creating a Bubble Chart 352 CS2 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 WE1 Counting Unique Words 364 PT1 Use Python Sets, Not Lists, for Efficient Set Operations 366 ST1 Hashing 367 CS1 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 ST2 Iterating over Dictionary Items 374 ST3 Storing Data Records 375 WE2 Translating Text Messages 375 8.3 Complex Structures 378 A Dictionary of Sets 378 A Dictionary of Lists 381 ST4 User Modules 383 WE3 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 PT1 Make All Instance Variables Private, Most Methods Public 402 9.5 Constructors 402 CE1 Trying to Call a Constructor 404 ST1 Default and Named Arguments 404 9.6 Implementing Methods 405 PT2 Define Instance Variables Only in the Constructor 407 ST2 Class Variables 408 9.7 Testing a Class 409 HT1 Implementing a Class 410 WE1 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 CS1 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 ST3 Object Types and Instances 435 WE2 GRAPHICS: A Die Class 436 CS2 Open Source and Free Software 439 10 Inheritance 443 10.1 Inheritance Hierarchies 444 PT1 Use a Single Class for Variation in Values, Inheritance for Variation in Behavior 447 ST1 The Cosmic Superclass: object 447 10.2 Implementing Subclasses 449 CE1 Confusing Super- and Subclasses 451 10.3 Calling the Superclass Constructor 452 10.4 Overriding Methods 455 CE2 Forgetting to Use the super Function When Invoking a Superclass Method 458 10.5 Polymorphism 458 ST2 Subclasses and Instances 461 ST3 Dynamic Method Lookup 461 ST4 Abstract Classes 462 CE3 Don’t Use Type Tests 463 HT1 Developing an Inheritance Hierarchy 463 WE1 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 CE1 Infinite Recursion 493 ST1 Recursion with Objects 493 11.2 PROBLEM SOLVING: Thinking Recursively 494 WE1 Finding Files 497 11.3 Recursive Helper Functions 498 11.4 The Efficiency of Recursion 499 11.5 Permutations 504 CS1 The Limits of Computation 506 11.6 Backtracking 508 WE2 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 ST1 Oh, Omega, and Theta 531 ST2 Insertion Sort 532 12.4 Merge Sort 534 12.5 Analyzing the Merge Sort Algorithm 536 ST3 The Quicksort Algorithm 538 CS1 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 PT1 Searching and Sorting 549 ST4 Comparing Objects 549 WE1 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

This book is authorized for sale in Europe, Africa and the Middle East only and may not be exported. The content is materially different than products for other markets including the authorized U.S. counterpart of this title. Exportation of this book to another region without the Publisher’s authorization may be illegal and a violation of the Publisher’s rights. The Publisher may take legal action to enforce its rights.