Contents

1 Computers and Programs 1

1.1 The Universal 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 Development Process 13

2.2 Example Program: Temperature Converter 13

2.3 Elements of Programs 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

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

8 Control Structures, Part 2 119

8.1 For Loops: A Quick Review 119

8.2 Indefinite Loops 120

8.3 Common Loop Patterns 121

8.3.1 Interactive 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-Level Design 140

9.3.2 Separation of Concerns 141

9.3.3 Second-Level Design 142

9.3.4 Designing simNGames 143

9.3.5 Third-Level 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 Development 150

9.5.2 The Art of Design 151

9.6 Exercises 152

10 Defining Classes 155

10.1 Quick Review 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 New 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

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 Frequency 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 Developing 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 Recursive Problem-Solving 228

13.2.1 Recursive Definitions 229

13.2.2 Recursive Functions 230

13.2.3 Recursive Search 230

13.3 Sorting Algorithms 231

13.3.1 Naive Sorting: Selection Sort 231

13.3.2 Divide and Conquer: Merge Sort 232

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

Was this article helpful?

0 0

Post a comment