How to think like a computer scientist : learning with Python

"How to Think Like a Computer Scientist: Learning with Python" is an introduction to computer science using the Python programming language. It covers the basics of computer programming, including variables and values, functions, conditionals and control flow, program development and debugging. Later chapters cover basic algorithms and data structures. Foreword 5 Preface 7 How and why I came to use Python 7 Finding a textbook 8 Introducing programming with Python 9 Building a community 11 Contributor List 13 Contents 17 The way of the program 27 1.1 The Python programming language 27 1.2 What is a program? 29 1.3 What is debugging? 30 1.3.1 Syntax errors 30 1.3.2 Runtime errors 31 1.3.3 Semantic errors 31 1.3.4 Experimental debugging 31 1.4 Formal and natural languages 32 1.5 The ̄rst program 34 1.6 Glossary 34 Variables, expressions and statements 37 2.1 Values and types 37 2.2 Variables 38 2.3 Variable names and keywords 39 2.4 Statements 40 2.5 Evaluating expressions 41 2.6 Operators and operands 42 2.7 Order of operations 42 2.8 Operations on strings 43 2.9 Composition 44 2.10 Comments 44 2.11 Glossary 45 Functions 47 3.1 Function calls 47 3.2 Type conversion 48 3.3 Type coercion 48 3.4 Math functions 49 3.5 Composition 50 3.6 Adding new functions 51 3.7 De ̄nitions and use 53 3.8 Flow of execution 54 3.9 Parameters and arguments 54 3.10 Variables and parameters are local 56 3.11 Stack diagrams 56 3.12 Functions with results 58 3.13 Glossary 58 Conditionals and recursion 61 4.1 The modulus operator 61 4.2 Boolean expressions 61 4.3 Logical operators 62 4.4 Conditional execution 63 4.5 Alternative execution 63 4.6 Chained conditionals 64 4.7 Nested conditionals 65 4.8 The return statement 66 4.9 Recursion 66 4.10 Stack diagrams for recursive functions 68 4.11 In ̄nite recursion 69 4.12 Keyboard input 69 4.13 Glossary 70 Fruitful functions 73 5.1 Return values 73 5.2 Program development 74 5.3 Composition 77 5.4 Boolean functions 78 5.5 More recursion 79 5.6 Leap of faith 81 5.7 One more example 82 5.8 Checking types 83 5.9 Glossary 84 Iteration 85 6.1 Multiple assignment 85 6.2 The while statement 86 6.3 Tables 88 6.4 Two-dimensional tables 90 6.5 Encapsulation and generalization 91 6.6 More encapsulation 92 6.7 Local variables 93 6.8 More generalization 94 6.9 Functions 95 6.10 Glossary 96 Strings 97 7.1 A compound data type 97 7.2 Length 98 7.3 Traversal and the for loop 98 7.4 String slices 100 7.5 String comparison 100 7.6 Strings are immutable 101 7.7 A find function 102 7.8 Looping and counting 102 7.9 The string module 103 7.10 Character classi ̄cation 104 7.11 Glossary 105 Lists 107 8.1 List values 107 8.2 Accessing elements 108 8.3 List length 109 8.4 List membership 110 8.5 Lists and for loops 110 8.6 List operations 111 8.7 List slices 112 8.8 Lists are mutable 112 8.9 List deletion 113 8.10 Objects and values 114 8.11 Aliasing 115 8.12 Cloning lists 115 8.13 List parameters 116 8.14 Nested lists 117 8.15 Matrixes 117 8.16 Strings and lists 118 8.17 Glossary 119 Tuples 121 9.1 Mutability and tuples 121 9.2 Tuple assignment 122 9.3 Tuples as return values 123 9.4 Random numbers 123 9.5 List of random numbers 124 9.6 Counting 125 9.7 Many buckets 126 9.8 A single-pass solution 128 9.9 Glossary 129 Dictionaries 131 10.1 Dictionary operations 132 10.2 Dictionary methods 133 10.3 Aliasing and copying 134 10.4 Sparse matrices 134 10.5 Hints 135 10.6 Long integers 137 10.7 Counting letters 138 10.8 Glossary 138 Files and exceptions 141 11.1 Text ̄les 143 11.2 Writing variables 144 11.3 Directories 147 11.4 Pickling 147 11.5 Exceptions 148 11.6 Glossary 150 Classes and objects 153 12.1 User-de ̄ned compound types 153 12.2 Attributes 154 12.3 Instances as parameters 155 12.4 Sameness 155 12.5 Rectangles 157 12.6 Instances as return values 158 12.7 Objects are mutable 158 12.8 Copying 159 12.9 Glossary 161 Classes and functions 163 13.1 Time 163 13.2 Pure functions 164 13.3 Modi ̄ers 165 13.4 Which is better? 166 13.5 Prototype development versus planning 167 13.6 Generalization 168 13.7 Algorithms 168 13.8 Glossary 169 Classes and methods 171 14.1 Object-oriented features 171 14.2 printTime 172 14.3 Another example 173 14.4 A more complicated example 174 14.5 Optional arguments 175 14.6 The initialization method 176 14.7 Points revisited 177 14.8 Operator overloading 178 14.9 Polymorphism 179 14.10 Glossary 181 Sets of objects 183 15.1 Composition 183 15.2 Card objects 183 15.3 Class attributes and the str method 185 15.4 Comparing cards 186 15.5 Decks 187 15.6 Printing the deck 187 15.7 Shu2ing the deck 189 15.8 Removing and dealing cards 190 15.9 Glossary 191 Inheritance 193 16.1 Inheritance 193 16.2 A hand of cards 194 16.3 Dealing cards 195 16.4 Printing a Hand 195 16.5 The CardGame class 197 16.6 OldMaidHand class 197 16.7 OldMaidGame class 199 16.8 Glossary 203 Linked lists 205 17.1 Embedded references 205 17.2 The Node class 205 17.3 Lists as collections 207 17.4 Lists and recursion 208 17.5 In ̄nite lists 209 17.6 The fundamental ambiguity theorem 210 17.7 Modifying lists 210 17.8 Wrappers and helpers 211 17.9 The LinkedList class 212 17.10 Invariants 213 17.11 Glossary 214 Stacks 215 18.1 Abstract data types 215 18.2 The Stack ADT 216 18.3 Implementing stacks with Python lists 216 18.4 Pushing and popping 217 18.5 Using a stack to evaluate post ̄x 218 18.6 Parsing 218 18.7 Evaluating post ̄x 219 18.8 Clients and providers 220 18.9 Glossary 221 Queues 223 19.1 The Queue ADT 223 19.2 Linked Queue 224 19.3 Performance characteristics 225 19.4 Improved Linked Queue 225 19.5 Priority queue 227 19.6 The Golfer class 229 19.7 Glossary 230 Trees 231 20.1 Building trees 232 20.2 Traversing trees 233 20.3 Expression trees 233 20.4 Tree traversal 234 20.5 Building an expression tree 236 20.6 Handling errors 240 20.7 The animal tree 240 20.8 Glossary 243 Debugging 245 A.1 Syntax errors 245 A.1.1 I can't get my program to run no matter what I do. 247 A.2 Runtime errors 247 A.2.1 My program does absolutely nothing. 247 A.2.2 My program hangs. 247 A.2.3 When I run the program I get an exception. 249 A.2.4 I added so many print statements I get inundated 250 with output. 250 A.3 Semantic errors 251 A.3.1 My program doesn't work. 251 A.3.2 I've got a big hairy expression and it doesn't do 252 what I expect. 252 A.3.3 I've got a function or method that doesn't return 253 what I expect. 253 A.3.4 I'm really, really stuck and I need help. 253 A.3.5 No, I really need help. 253 Creating a new data type 255 B.1 Fraction multiplication 256 B.2 Fraction addition 258 B.3 Euclid's algorithm 258 B.4 Comparing fractions 259 B.5 Taking it further 260 B.6 Glossary 261 Recommendations for further reading 263 C.1 Python-related web sites and books 264 C.2 Recommended general computer science 265 books 265 GNU Free Documentation 267 License 267 Preamble 267 D.1 Applicability and De ̄nitions 268 D.2 Verbatim Copying 269 D.3 Copying in Quantity 269 D.4 Modi ̄cations 270 D.5 Combining Documents 272 D.6 Collections of Documents 273 D.7 Aggregation with Independent Works 273 D.8 Translation 273 D.9 Termination 274 D.10 Future Revisions of This License 274 D.11 Addendum: How to Use This License for 274 Your Documents 274 Index 277 Foreword......Page 5 How and why I came to use Python......Page 7 Finding a textbook......Page 8 Introducing programming with Python......Page 9 Building a community......Page 11 Contributor List......Page 13 Contents......Page 17 1.1 The Python programming language......Page 27 1.2 What is a program?......Page 29 1.3.1 Syntax errors......Page 30 1.3.4 Experimental debugging......Page 31 1.4 Formal and natural languages......Page 32 1.6 Glossary......Page 34 2.1 Values and types......Page 37 2.2 Variables......Page 38 2.3 Variable names and keywords......Page 39 2.4 Statements......Page 40 2.5 Evaluating expressions......Page 41 2.7 Order of operations......Page 42 2.8 Operations on strings......Page 43 2.10 Comments......Page 44 2.11 Glossary......Page 45 3.1 Function calls......Page 47 3.3 Type coercion......Page 48 3.4 Math functions......Page 49 3.5 Composition......Page 50 3.6 Adding new functions......Page 51 3.7 De ̄nitions and use......Page 53 3.9 Parameters and arguments......Page 54 3.11 Stack diagrams......Page 56 3.13 Glossary......Page 58 4.2 Boolean expressions......Page 61 4.3 Logical operators......Page 62 4.5 Alternative execution......Page 63 4.6 Chained conditionals......Page 64 4.7 Nested conditionals......Page 65 4.9 Recursion......Page 66 4.10 Stack diagrams for recursive functions......Page 68 4.12 Keyboard input......Page 69 4.13 Glossary......Page 70 5.1 Return values......Page 73 5.2 Program development......Page 74 5.3 Composition......Page 77 5.4 Boolean functions......Page 78 5.5 More recursion......Page 79 5.6 Leap of faith......Page 81 5.7 One more example......Page 82 5.8 Checking types......Page 83 5.9 Glossary......Page 84 6.1 Multiple assignment......Page 85 6.2 The while statement......Page 86 6.3 Tables......Page 88 6.4 Two-dimensional tables......Page 90 6.5 Encapsulation and generalization......Page 91 6.6 More encapsulation......Page 92 6.7 Local variables......Page 93 6.8 More generalization......Page 94 6.9 Functions......Page 95 6.10 Glossary......Page 96 7.1 A compound data type......Page 97 7.3 Traversal and the for loop......Page 98 7.5 String comparison......Page 100 7.6 Strings are immutable......Page 101 7.8 Looping and counting......Page 102 7.9 The string module......Page 103 7.10 Character classi ̄cation......Page 104 7.11 Glossary......Page 105 8.1 List values......Page 107 8.2 Accessing elements......Page 108 8.3 List length......Page 109 8.5 Lists and for loops......Page 110 8.6 List operations......Page 111 8.8 Lists are mutable......Page 112 8.9 List deletion......Page 113 8.10 Objects and values......Page 114 8.12 Cloning lists......Page 115 8.13 List parameters......Page 116 8.15 Matrixes......Page 117 8.16 Strings and lists......Page 118 8.17 Glossary......Page 119 9.1 Mutability and tuples......Page 121 9.2 Tuple assignment......Page 122 9.4 Random numbers......Page 123 9.5 List of random numbers......Page 124 9.6 Counting......Page 125 9.7 Many buckets......Page 126 9.8 A single-pass solution......Page 128 9.9 Glossary......Page 129 Dictionaries......Page 131 10.1 Dictionary operations......Page 132 10.2 Dictionary methods......Page 133 10.4 Sparse matrices......Page 134 10.5 Hints......Page 135 10.6 Long integers......Page 137 10.8 Glossary......Page 138 Files and exceptions......Page 141 11.1 Text ̄les......Page 143 11.2 Writing variables......Page 144 11.4 Pickling......Page 147 11.5 Exceptions......Page 148 11.6 Glossary......Page 150 12.1 User-de ̄ned compound types......Page 153 12.2 Attributes......Page 154 12.4 Sameness......Page 155 12.5 Rectangles......Page 157 12.7 Objects are mutable......Page 158 12.8 Copying......Page 159 12.9 Glossary......Page 161 13.1 Time......Page 163 13.2 Pure functions......Page 164 13.3 Modi ̄ers......Page 165 13.4 Which is better?......Page 166 13.5 Prototype development versus planning......Page 167 13.7 Algorithms......Page 168 13.8 Glossary......Page 169 14.1 Object-oriented features......Page 171 14.2 printTime......Page 172 14.3 Another example......Page 173 14.4 A more complicated example......Page 174 14.5 Optional arguments......Page 175 14.6 The initialization method......Page 176 14.7 Points revisited......Page 177 14.8 Operator overloading......Page 178 14.9 Polymorphism......Page 179 14.10 Glossary......Page 181 15.2 Card objects......Page 183 15.3 Class attributes and the str method......Page 185 15.4 Comparing cards......Page 186 15.6 Printing the deck......Page 187 15.7 Shu2ing the deck......Page 189 15.8 Removing and dealing cards......Page 190 15.9 Glossary......Page 191 16.1 Inheritance......Page 193 16.2 A hand of cards......Page 194 16.4 Printing a Hand......Page 195 16.6 OldMaidHand class......Page 197 16.7 OldMaidGame class......Page 199 16.8 Glossary......Page 203 17.2 The Node class......Page 205 17.3 Lists as collections......Page 207 17.4 Lists and recursion......Page 208 17.5 In ̄nite lists......Page 209 17.7 Modifying lists......Page 210 17.8 Wrappers and helpers......Page 211 17.9 The LinkedList class......Page 212 17.10 Invariants......Page 213 17.11 Glossary......Page 214 18.1 Abstract data types......Page 215 18.3 Implementing stacks with Python lists......Page 216 18.4 Pushing and popping......Page 217 18.6 Parsing......Page 218 18.7 Evaluating post ̄x......Page 219 18.8 Clients and providers......Page 220 18.9 Glossary......Page 221 19.1 The Queue ADT......Page 223 19.2 Linked Queue......Page 224 19.4 Improved Linked Queue......Page 225 19.5 Priority queue......Page 227 19.6 The Golfer class......Page 229 19.7 Glossary......Page 230 Trees......Page 231 20.1 Building trees......Page 232 20.3 Expression trees......Page 233 20.4 Tree traversal......Page 234 20.5 Building an expression tree......Page 236 20.7 The animal tree......Page 240 20.8 Glossary......Page 243 A.1 Syntax errors......Page 245 A.2.2 My program hangs.......Page 247 A.2.3 When I run the program I get an exception.......Page 249 with output.......Page 250 A.3.1 My program doesn't work.......Page 251 what I expect.......Page 252 A.3.5 No, I really need help.......Page 253 Creating a new data type......Page 255 B.1 Fraction multiplication......Page 256 B.3 Euclid's algorithm......Page 258 B.4 Comparing fractions......Page 259 B.5 Taking it further......Page 260 B.6 Glossary......Page 261 Recommendations for further reading......Page 263 C.1 Python-related web sites and books......Page 264 books......Page 265 Preamble......Page 267 D.1 Applicability and De ̄nitions......Page 268 D.3 Copying in Quantity......Page 269 D.4 Modi ̄cations......Page 270 D.5 Combining Documents......Page 272 D.8 Translation......Page 273 Your Documents......Page 274 Index......Page 277