xxiv Contents 11.4 Pickling··········· 123 11.5 Exceptions,···· 124 11.6 Glossary······ 126 12 Classes and objects 129 12.1 User-defined compound types . 129 12.2 Attributes......... 。。 130 12.3 Instances as arguments... 131 12.4 Sameness....·.··· 131 12.5 Rectangles....·.·· 4 133 12.6 Instances as return values 134 12.7 Objects are mutable 134 12.8 Copying 135 12.9 Glossary···· 137 13 Classes and functions 139 13.1 Time.······· 4 139 13.2 Pure functions... 44 140 13.3 Modifiers 44 141 13.4 Which is better? 142 13.5 Prototype development versus planning 143 13.6 Generalization.... 144 13.7 Algorithms 。。 144 13.8 Glossary .... 145 14 Classes and methods 147 14.1 Object-oriented features.. 147 14.2 printTime.···· 148 14.3 Another example 。。。 149
xxiv Contents 11.4 Pickling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 11.5 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 11.6 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 12 Classes and objects 129 12.1 User-defined compound types . . . . . . . . . . . . . . . . . . . . 129 12.2 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 12.3 Instances as arguments . . . . . . . . . . . . . . . . . . . . . . . . 131 12.4 Sameness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 12.5 Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 12.6 Instances as return values . . . . . . . . . . . . . . . . . . . . . . 134 12.7 Objects are mutable . . . . . . . . . . . . . . . . . . . . . . . . . 134 12.8 Copying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 12.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 13 Classes and functions 139 13.1 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 13.2 Pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 13.3 Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 13.4 Which is better? . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 13.5 Prototype development versus planning . . . . . . . . . . . . . . 143 13.6 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 13.7 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 13.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 14 Classes and methods 147 14.1 Object-oriented features . . . . . . . . . . . . . . . . . . . . . . . 147 14.2 printTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 14.3 Another example . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Contents XXV 14.4 A more complicated example 150 14.5 Optional arguments.···· 151 14.6 The initialization method 152 14.7 Points revisited..... 153 14.8 Operator overloading.... 154 14.9 Polymorphism...·. 155 14.10G1 lossary.·.···· 157 15 Sets of objects 159 15.1 Composition...... 159 15.2 Card objects.......... 159 15.3 Class attributes and the_str__method 161 15.4 Comparing cards 162 15.5 Decks 163 15.6 Printing the deck 163 15.7 Shuffling the deck.···· 165 15.8 Removing and dealing cards 166 15.9 Glossary.········ 167 16 Inheritance 169 16.1 Inheritance... 169 16.2 A hand of cards ... 170 16.3 Dealing cards .... 171 16.4 Printing a Hand... 171 16.5 The CardGame class.. 172 16.6 01dMaidHand class 173 16.7 0ldMaidGame class .. 175 16.8 Glossary······ 179
Contents xxv 14.4 A more complicated example . . . . . . . . . . . . . . . . . . . . 150 14.5 Optional arguments . . . . . . . . . . . . . . . . . . . . . . . . . . 151 14.6 The initialization method . . . . . . . . . . . . . . . . . . . . . . 152 14.7 Points revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 14.8 Operator overloading . . . . . . . . . . . . . . . . . . . . . . . . . 154 14.9 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 14.10 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 15 Sets of objects 159 15.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 15.2 Card objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 15.3 Class attributes and the str method . . . . . . . . . . . . . . 161 15.4 Comparing cards . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 15.5 Decks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 15.6 Printing the deck . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 15.7 Shuffling the deck . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 15.8 Removing and dealing cards . . . . . . . . . . . . . . . . . . . . . 166 15.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 16 Inheritance 169 16.1 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 16.2 A hand of cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 16.3 Dealing cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 16.4 Printing a Hand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 16.5 The CardGame class . . . . . . . . . . . . . . . . . . . . . . . . . . 172 16.6 OldMaidHand class . . . . . . . . . . . . . . . . . . . . . . . . . . 173 16.7 OldMaidGame class . . . . . . . . . . . . . . . . . . . . . . . . . . 175 16.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
xxvi Contents 17 Linked lists 181 17.1 Embedded references ... 181 17.2 The Node class....... 181 17.3 Lists as collections 183 17.4 Lists and recursion..... 184 17.5 Infinite lists········· 185 17.6 The fundamental ambiguity theorem . 186 17.7 Modifying lists 186 17.8 Wrappers and helpers 187 17.9 The LinkedList class 4 188 17.10 Invariants... 189 17.11 Glossary.... 4 190 18 Stacks 191 18.1 Abstract data types···· 191 18.2 The Stack ADT.··.·.· 192 18.3 Implementing stacks with Python lists 192 18.4 Pushing and popping。。················· 193 18.5 Using a stack to evaluate postfix 194 18.6 Parsing.···· 4 194 18.7 Evaluating postfix 195 18.8 Clients and providers.. 196 18.9 Glossary···· 4 197 19 Queues 199 19.1 The Queue ADT.... 199 19.2 Linked Queue...····· 200 19.3 Performance characteristics 201
xxvi Contents 17 Linked lists 181 17.1 Embedded references . . . . . . . . . . . . . . . . . . . . . . . . . 181 17.2 The Node class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 17.3 Lists as collections . . . . . . . . . . . . . . . . . . . . . . . . . . 183 17.4 Lists and recursion . . . . . . . . . . . . . . . . . . . . . . . . . . 184 17.5 Infinite lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 17.6 The fundamental ambiguity theorem . . . . . . . . . . . . . . . . 186 17.7 Modifying lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 17.8 Wrappers and helpers . . . . . . . . . . . . . . . . . . . . . . . . 187 17.9 The LinkedList class . . . . . . . . . . . . . . . . . . . . . . . . 188 17.10 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 17.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 18 Stacks 191 18.1 Abstract data types . . . . . . . . . . . . . . . . . . . . . . . . . 191 18.2 The Stack ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 18.3 Implementing stacks with Python lists . . . . . . . . . . . . . . . 192 18.4 Pushing and popping . . . . . . . . . . . . . . . . . . . . . . . . . 193 18.5 Using a stack to evaluate postfix . . . . . . . . . . . . . . . . . . 194 18.6 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 18.7 Evaluating postfix . . . . . . . . . . . . . . . . . . . . . . . . . . 195 18.8 Clients and providers . . . . . . . . . . . . . . . . . . . . . . . . . 196 18.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 19 Queues 199 19.1 The Queue ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 19.2 Linked Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 19.3 Performance characteristics . . . . . . . . . . . . . . . . . . . . . 201
Contents xxvii 19.4 Improved Linked Queue..... 201 19.5 Priority queue···· 203 19.6 The Golfer class 205 19.7 Glossary··· 206 20 Trees 207 20.1 Building trees···· 208 20.2 Traversing trees·.· 209 20.3 Expression trees.... 209 20.4 Tree traversal·.····· 210 20.5 Building an expression tree 212 20.6 Handling errors······ 216 20.7 The animal tree... 216 20.8 Glossary·· 219 A Debugging 221 A.1 Syntax errors 221 A.2 Runtime errors··· 223 A.3 Semantic errors.... 227 B Creating a new data type 231 B.1 Fraction multiplication 232 B.2 Fraction addition .. 234 B.3 Euclid's algorithm·.· 234 B.4 Comparing fractions 235 B.5 Taking it further.... 236 B.6 Glossary。··········· 236 C Recommendations for further reading 239 C.1 Python-related web sites and books,················ 240 C.2 Recommended general computer science books..........241
Contents xxvii 19.4 Improved Linked Queue . . . . . . . . . . . . . . . . . . . . . . . 201 19.5 Priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 19.6 The Golfer class . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 19.7 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 20 Trees 207 20.1 Building trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 20.2 Traversing trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 20.3 Expression trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 20.4 Tree traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 20.5 Building an expression tree . . . . . . . . . . . . . . . . . . . . . 212 20.6 Handling errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 20.7 The animal tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 20.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 A Debugging 221 A.1 Syntax errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.2 Runtime errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 A.3 Semantic errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 B Creating a new data type 231 B.1 Fraction multiplication . . . . . . . . . . . . . . . . . . . . . . . . 232 B.2 Fraction addition . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 B.3 Euclid’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 234 B.4 Comparing fractions . . . . . . . . . . . . . . . . . . . . . . . . . 235 B.5 Taking it further . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 B.6 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 C Recommendations for further reading 239 C.1 Python-related web sites and books . . . . . . . . . . . . . . . . . 240 C.2 Recommended general computer science books . . . . . . . . . . 241
Chapter 1 The way of the program The goal of this book is to teach you to think like a computer scientist.This way of thinking combines some of the best features of mathematics,engineering,and natural science.Like mathematicians,computer scientists use formal languages to denote ideas (specifically computations).Like engineers,they design things, assembling components into systems and evaluating tradeoffs among alternatives. Like scientists,they observe the behavior of complex systems,form hypotheses, and test predictions. The single most important skill for a computer scientist is problem solving. Problem solving means the ability to formulate problems,think creatively about solutions,and express a solution clearly and accurately.As it turns out,the process of learning to program is an excellent opportunity to practice problem- solving skills.That's why this chapter is called,"The way of the program." On one level,you will be learning to program,a useful skill by itself.On another level,you will use programming as a means to an end.As we go along,that end will become clearer. 1.1 The Python programming language The programming language you will be learning is Python.Python is an example of a high-level language;other high-level languages you might have heard of are C,C++,Perl,and Java. As you might infer from the name "high-level language,"there are also low- level languages,sometimes referred to as "machine languages"or "assembly
Chapter 1 The way of the program The goal of this book is to teach you to think like a computer scientist. This way of thinking combines some of the best features of mathematics, engineering, and natural science. Like mathematicians, computer scientists use formal languages to denote ideas (specifically computations). Like engineers, they design things, assembling components into systems and evaluating tradeoffs among alternatives. Like scientists, they observe the behavior of complex systems, form hypotheses, and test predictions. The single most important skill for a computer scientist is problem solving. Problem solving means the ability to formulate problems, think creatively about solutions, and express a solution clearly and accurately. As it turns out, the process of learning to program is an excellent opportunity to practice problemsolving skills. That’s why this chapter is called, “The way of the program.” On one level, you will be learning to program, a useful skill by itself. On another level, you will use programming as a means to an end. As we go along, that end will become clearer. 1.1 The Python programming language The programming language you will be learning is Python. Python is an example of a high-level language; other high-level languages you might have heard of are C, C++, Perl, and Java. As you might infer from the name “high-level language,” there are also lowlevel languages, sometimes referred to as “machine languages” or “assembly