iv CONTENTS l0.5.4 The Main Program....,,.,,..,·,,.,.,.,..· 172 10.6 Exercises 173 11 Data Collections 177 ll.1 Example Problem:Simple Statistics,.,,,,,,,···,,,,·····, 177 112 Applying Lists,·············,,···…·· 178 ll2.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 00 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 l3.3.2 Divide and Conquer:Merge Sort.,,···········,·,·· 232i 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