AllenB.Downey November2012

1 How to think like a computer scientist Allen B. Downey November 2012. 2. How to think like a computer scientist C++ Version Copyright (C) 2012 Allen B. Downey Permission is granted to copy, distribute, and/or modify this document un- der the terms of the Creative Commons Attribution-NonCommercial Un- ported License, which is available at by- The original form of this book is LATEX source code. Compiling this code has the effect of generating a device-independent representation of a textbook, which can be converted to other formats and printed.

2 This book was typeset by the author using latex, dvips and ps2pdf, among other free, open-source programs. The LaTeX source for this book is avail- able from and from the SVN repository Contents 1 The way of the program 1. What is a programming language? .. 1. What is a program? .. 3. What is debugging? .. 4. Compile-time errors .. 4. Run-time errors .. 4. Logic errors and semantics .. 4. Experimental debugging .. 5. Formal and natural languages .. 5. The first program .. 7. Glossary .. 8. 2 Variables and types 11.

3 More output .. 11. Values .. 12. Variables .. 13. Assignment .. 13. Outputting variables .. 14. Keywords .. 15. Operators .. 16. Order of operations .. 17. Operators for characters .. 17. Composition .. 18. Glossary .. 18. 3 Function 21. Floating-point .. 21. Converting from double to int .. 22. Math functions .. 23. Composition .. 24. Adding new functions .. 24. Definitions and uses .. 26. Programs with multiple functions .. 27. Parameters and arguments .. 28. i ii CONTENTS. Parameters and variables are local.

4 29. Functions with multiple parameters .. 30. Functions with results .. 30. Glossary .. 31. 4 Conditionals and recursion 33. The modulus operator .. 33. Conditional execution .. 33. Alternative execution .. 34. Chained conditionals .. 35. Nested conditionals .. 35. The return statement .. 36. Recursion .. 36. Infinite recursion .. 39. Stack diagrams for recursive functions .. 39. Glossary .. 40. 5 Fruitful functions 41. Return values .. 41. Program development .. 43. Composition .. 45. Overloading.

5 46. Boolean values .. 47. Boolean variables .. 47. Logical operators .. 48. Bool functions .. 48. Returning from main .. 49. More recursion .. 50. Leap of faith .. 52. One more example .. 53. Glossary .. 53. 6 Iteration 55. Multiple assignment .. 55. Iteration .. 56. The while statement .. 56. Tables .. 58. Two-dimensional tables .. 60. Encapsulation and generalization .. 60. Functions .. 61. More encapsulation .. 62. Local variables .. 62. More generalization .. 63. Glossary .. 65. CONTENTS iii 7 Strings and things 67.

6 Containers for strings .. 67. string variables .. 67. Extracting characters from a string .. 68. Length .. 68. Traversal .. 69. A run-time error .. 70. The find function .. 70. Our own version of find .. 71. Looping and counting .. 71. Increment and decrement operators .. 72. String concatenation .. 72. strings are mutable .. 73. strings are comparable .. 74. Character classification .. 74. Other string functions .. 75. Glossary .. 75. 8 Structures 77. Compound values .. 77. Point objects .. 77. Accessing instance variables.

7 78. Operations on structures .. 79. Structures as parameters .. 80. Call by value .. 80. Call by reference .. 81. Rectangles .. 82. Structures as return types .. 84. Passing other types by reference .. 84. Getting user input .. 85. Glossary .. 87. 9 More structures 89. Time .. 89. printTime .. 90. Functions for objects .. 90. Pure functions .. 91. const parameters .. 92. Modifiers .. 93. Fill-in functions .. 94. Which is best? .. 95. Incremental development versus planning .. 95. Generalization.

8 96. Algorithms .. 96. Glossary .. 97. iv CONTENTS. 10 Vectors 99. Accessing elements .. 100. Copying vectors .. 101. for loops .. 101. Vector size .. 102. Vector functions .. 103. Random numbers .. 103. Statistics .. 105. Vector of random numbers .. 105. Counting .. 106. the other values .. 107. histogram .. 108. single-pass solution .. 108. seeds .. 109.. 109. 11 Member functions 111. Objects and functions .. 111. print .. 112. Implicit variable access .. 113. Another example .. 114. Yet another example.

9 115. A more complicated example .. 115. Constructors .. 116. Initialize or construct? .. 117. One last example .. 117. files .. 118.. 121. 12 Vectors of Objects 123. Composition .. 123. Card objects .. 123. The printCard function .. 125. The equals function .. 127. The isGreater function .. 128. Vectors of cards .. 129. The printDeck function .. 131. Searching .. 131. Bisection search .. 132. and subdecks .. 135.. 135. CONTENTS v 13 Objects of Vectors 137. Enumerated types .. 137. switch statement.

10 138. Decks .. 140. Another constructor .. 141. Deck member functions .. 141. Shuffling .. 143. Sorting .. 143. Subdecks .. 144. Shuffling and dealing .. 145.. 145.. 147. 14 Classes and invariants 149. Private data and classes .. 149. What is a class? .. 150. Complex numbers .. 151. Accessor functions .. 153. Output .. 154. A function on Complex numbers .. 155. Another function on Complex numbers .. 155. Invariants .. 156. Preconditions .. 157. functions .. 159.. 160. 15 File Input/Output and apmatrixes 161.