Object-Oriented Programming in Python

Drs. Goldwasser and Letscher are on the Faculty in the Department of Mathematics and Computer Science at Saint Louis University.  Both are active in teaching the introductory computer science course for which this book was designed.  They have described the development of this material at the premier national and international conferences on Computer Science education. Dr. Goldwasser received his Ph.D. in Computer Science at Stanford University in 1997, and has taught courses at Stanford University, Princeton University, Loyola University of Chicago, and Colorado College before joining Saint Louis University. His research interests center around the design and analysis of algorithms. Dr. Letscher received his Ph.D. in Mathematics from the University of Michigan in 1997, and has taught courses in mathematics and computer science at the University of California San Diego, Oklahoma State University, and the American Institute of Mathematics before joining Saint Louis University. His primary research interests center around computational topology.

Preface

vii I Fundamental Topics 3 1 Cornerstones of Computing 5 1.1 Data and Types 5 1.2 Operations, Functions, and Algorithms 6 1.3 High-Level Programming Languages 10 1.4 The Object-Oriented Paradigm 12 1.5 Design and Modeling 23 1.6 Chapter Review 25 2 Getting Started in Python 31 2.1 The Python Interpreter 31 2.2 Using Objects: the list Class 32 2.3 Other Sequence Classes: str and tuple 49 2.4 Numeric Types: int, long, and float 58 2.5 Type Conversions 60 2.6 Calling Functions 61 2.7 Python Modules 62 2.8 Expressions 64 2.9 Using a File for Source Code 69 2.10 Case Study: Strings and Lists 75 2.11 Chapter Review 76 3 Getting Started with Graphics 89 3.1 The Canvas 90 3.2 Drawable Objects 93 3.3 Rotating, Scaling, and Flipping 103 3.4 Cloning 106 3.5 Case Study: Smiley Face 106 3.6 Layers 108 3.7 Animation 111 3.8 Graphical User Interfaces 113 3.9 Case Study: Flying Arrows 116 3.10 Chapter Review 120 4 Elementary Control Structures 125 4.1 For Loops 125 4.2 Case Study: DNA to RNA Transcription 135 4.3 Case Study: Drawing a Pyramid 136 4.4 Conditional Statements 140 4.5 List Comprehension 148 4.6 Chapter Review 149 5 Additional Control Structures 159 5.1 While Loops 160 5.2 Functions 166 5.3 Avoiding Duplicate Code 172 5.4 Case Study: Computing the Square Root 175 5.5 Error Checking and Exceptions 179 5.6 Case Study: Simulating a Chain under the Force of Gravity 185 5.7 Chapter Review 192 6 Defining Our Own Classes 203 6.1 A Simple Point Class 203 6.2 A Robust Point Class 207 6.3 A Television Class 214 6.4 A Fraction Class 222 6.5 Advanced Lessons 226 6.6 Chapter Review 229 7 Good Software Practices 237 7.1 Overview of Mastermind 237 7.2 Top-Down Design and Bottom-Up Implementation 238 7.3 Our Mastermind Design 239 7.4 Naming Conventions 244 7.5 Formal Documentation: Python Docstrings 246 7.6 Encapsulation of Implementation Details 250 7.7 Modules and Unit Testing 252 7.8 Error Checking 258 7.9 Mastermind: Pulling It Together 260 7.10 Flexibility in Design: Graphical Output 263 7.11 Chapter Review 266 8 Input, Output, and Files 271 8.1 Standard Input and Output 271 8.2 Formatted Strings 273 8.3 Working with Files 275 8.4 Handling Newline Characters 279 8.5 Case Studies 281 8.6 Chapter Review 292 9 Inheritance 299 9.1 Augmentation 300 9.2 Specialization 303 9.3 When Should Inheritance (Not) Be Used 308 9.4 Class Hierarchies and cs1graphics 310 9.5 Multiple Inheritance 318 9.6 Case Study: a Mailbox Class 321 9.7 Chapter Review 326 II Advanced Topics 331 10 Deeper Understanding of the Management of Objects 333 10.1 Understanding Objects and References 334 10.2 Objects that Reference Other Objects 341 10.3 Objects in the Context of a Function 348 10.4 Case Study: Subtleties in the cs1graphics Module 353 10.5 Chapter Review 356 11 Recursion 361 11.1 A Bullseye Class 362 11.2 Our Own List Implementation 368 11.3 Functional Recursion 374 11.4 Binary Search 376 11.5 Case Study: Solving a Puzzle 383 11.6 Chapter Review 388 12 More Python Containers 397 12.1 Two Familiar Containers: list and tuple 399 12.2 Dictionaries 401 12.3 Containers of Containers 406 12.4 Sets 409 12.5 Arrays 414 12.6 Python's Internal Use of Dictionaries 416 12.7 Case Study: a Simple Search Engine 422 12.8 Chapter Review 430 13 Implementing Data Structures 435 13.1 Measuring Efficiency 436 13.2 Python's list Class 438 13.3 Our Own Dictionary Implementation 441 13.4 Binary Search Trees 451 13.5 Chapter Review 461 14 Sorting Algorithms 467 14.1 Customizing Use of Python's Sort 467 14.2 Selection Sort 471 14.3 Insertion Sort 473 14.4 Merge Sort 475 14.5 Quicksort 482 14.6 Which Algorithm Does Python Use? 487 14.7 Chapter Review 488 15 Event-Driven Programming 493 15.1 Basics of Event-Driven Programming 494 15.2 Event Handling in Our Graphics Module 496 15.3 The Event Class 499 15.4 Programming Using Events 505 15.5 Case Study: a Full GUI for Mastermind 512 15.6 Chapter Review 519 16 Network Programming 521 16.1 A Network Primer 521 16.2 Writing a Basic Client 524 16.3 Basic Network Servers 529 16.4 Case Study: Network Chat Room 532 16.5 Peer-to-Peer: Instant Messenger 540 16.6 Server-Side Scripting and CGI 543 16.7 Case Study: Searching the Web 546 16.8 Chapter Review 553 Appendices 559 A Using IDLE 561 A.1 Using the Python Interpreter within IDLE 561 A.2 Working with Files 562 B Python, Java, and C++: a Transition Guide 565 B.1 The Purpose of This Guide 565 B.2 High-Level Programming Languages 566 B.3 A First Glance at Java and C++ 569 B.4 Java Guide 572 B.5 C++ Guide 599 C Solutions to Practice Exercises 625 D Glossary 649 Index 659