Python Programming: An Introduction to Computer Science

1 Computers and Programs 1 1.1 The Uni versal Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Program Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 What is Computer Science? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Hardware Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6 The Magic of Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.7 Inside a Python Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.8 Chaos and Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Writing Simple Programs 13 2.1 The Software De velopment Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Example Program: Temperature Converter . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Elements of Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Output Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Assignment Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.1 Simple Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.2 Assigning Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5.3 Simultaneous Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Definite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Example Program: Future Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Computing with Numbers 25 3.1 Numeric Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Using the Math Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 Accumulating Results: Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 The Limits of Int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Handling Large Numbers: Long Ints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4 Computing with Strings 39 4.1 The String Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Simple String Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3 Strings and Secret Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.1 String Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.2 Programming an Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3.3 Programming a Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3.4 Other String Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 i ii CONTENTS 4.3.5 From Encoding to Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.4 Output as String Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.1 Converting Numbers to Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.2 String Formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4.3 Better Change Counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 File Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5.1 Multi-Line Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5.2 File Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.5.3 Example Program: Batch Usernames . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.5.4 Coming Attraction: Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5 Objects and Graphics 61 5.1 The Object of Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.2 Graphics Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3 Using Graphical Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4 Graphing Future Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.5 Choosing Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.6 Interactive Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6.1 Getting Mouse Clicks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6.2 Handling Textual Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.7 Graphics Module Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7.1 GraphWin Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7.2 Graphics Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7.3 Entry Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.7.4 Displaying Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.7.5 Generating Colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6 Defining Functions 85 6.1 The Function of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2 Functions, Informally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.3 Future Value with a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.4 Functions and Parameters: The Gory Details . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.5 Functions that Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.6 Functions and Program Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7 Control Structures, Part 1 101 7.1 Simple Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.1.1 Example: Temperature Warnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.1.2 Forming Simple Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.1.3 Example: Conditional Program Execution . . . . . . . . . . . . . . . . . . . . . . . 104 7.2 Two-Way Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.3 Multi-Way Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.4 Exception Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.5 Study in Design: Max of Three . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7.5.1 Strategy 1: Compare Each to All . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7.5.2 Strategy 2: Decision Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.5.3 Strategy 3: Sequential Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.5.4 Strategy 4: Use Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.5.5 Some Lessons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 CONTENTS iii 8 Control Structures, Part 2 119 8.1 For Loops: A Quick Revie w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.2 Indefinite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8.3 Common Loop Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.3.1 Interacti v e Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.3.2 Sentinel Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 8.3.3 File Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 8.3.4 Nested Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 8.4 Computing with Booleans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.4.1 Boolean Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.4.2 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 8.5 Other Common Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.5.1 Post-Test Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.5.2 Loop and a Half . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.5.3 Boolean Expressions as Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9 Simulation and Design 137 9.1 Simulating Racquetball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9.1.1 A Simulation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9.1.2 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.2 Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.3 Top-Down Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.3.1 Top-Le vel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.3.2 Separation of Concerns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 9.3.3 Second-Le vel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 9.3.4 Designing simNGames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 9.3.5 Third-Le vel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 9.3.6 Finishing Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.3.7 Summary of the Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4 Bottom-Up Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4.1 Unit Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 9.5 Other Design Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 9.5.1 Prototyping and Spiral De velopment . . . . . . . . . . . . . . . . . . . . . . . . . . 150 9.5.2 The Art of Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 10 Defining Classes 155 10.1 Quick Revie w of Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 10.2 Example Program: Cannonball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.2.1 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.2.2 Designing the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.2.3 Modularizing the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.3 Defining Ne w Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.3.1 Example: Multi-Sided Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 10.3.2 Example: The Projectile Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 10.4 Objects and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 10.4.1 Encapsulating Useful Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 10.4.2 Putting Classes in Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 10.5 Widget Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 10.5.1 Example Program: Dice Roller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 10.5.2 Building Buttons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 10.5.3 Building Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 i v CONTENTS 10.5.4 The Main Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 11 Data Collections 177 11.1 Example Problem: Simple Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 11.2 Applying Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.2.1 Lists are Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.2.2 Lists vs. Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.2.3 List Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 11.3 Statistics with Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.4 Combining Lists and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 11.5 Case Study: Python Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.1 A Calculator as an Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.2 Constructing the Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.3 Processing Buttons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 11.6 Non-Sequential Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 11.6.1 Dictionary Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 11.6.2 Dictionary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.6.3 Example Program: Word Frequenc y . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 12 Object-Oriented Design 201 12.1 The Process of OOD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 12.2 Case Study: Racquetball Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 12.2.1 Candidate Objects and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.2 Implementing SimStats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.3 Implementing RBallGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 12.2.4 Implementing Player . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.2.5 The Complete Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.3 Case Study: Dice Poker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.1 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.2 Identifying Candidate Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.3 Implementing the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 12.3.4 A Text-Based UI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 12.3.5 De veloping a GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 12.4 OO Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.4.1 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.4.2 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.4.3 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 13 Algorithm Analysis and Design 225 13.1 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 13.1.1 A Simple Searching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 13.1.2 Strategy 1: Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 13.1.3 Strategy 2: Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 13.1.4 Comparing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 13.2 Recursi v e Problem-Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 13.2.1 Recursi v e Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 13.2.2 Recursi v e Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 13.2.3 Recursi v e Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 13.3 Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.3.1 Nai v e Sorting: Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.3.2 Divide and Conquer: Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 CONTENTS v 13.3.3 Comparing Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 13.4 Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 13.4.1 Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 13.4.2 The Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 13.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241