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...