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. 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.

2 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. 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 .. 29. Functions with multiple parameters .. 30. Functions with results .. 30. Glossary .. 31. 4 Conditionals and recursion 33. The modulus operator .. 33. Conditional execution.

3 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 .. 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. Containers for strings.

4 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 .. 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.

5 Modifiers .. 93. Fill-in functions .. 94. Which is best? .. 95. Incremental development versus planning .. 95. Generalization .. 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 .. 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.

6 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 .. 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. Streams .. 161. File input .. 162. File output .. 163. Parsing input .. 163. Parsing numbers .. 165.

7 The Set data structure .. 166. apmatrix .. 169. A distance matrix .. 170. A proper distance matrix .. 171.. 173. A Quick reference for AP classes 175. apstring .. 175. apvector .. 176. apmatrix .. 177. vi CONTENTS. Chapter 1. The way of the program The goal of this book is to teach you to think like a computer scientist. I like the way computer scientists think because they combine some of the best fea- tures of Mathematics, Engineering, and Natural Science. Like mathematicians, computer scientists use formal languages to denote ideas (specifically computa- tions). 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. By that I mean the ability to formulate problems, think creatively about solu- tions, and express a solution clearly and accurately.

8 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.. Of course, the other goal of this book is to prepare you for the Computer Science AP Exam. We may not take the most direct approach to that goal, though. For example, there are not many exercises in this book that are similar to the AP questions. On the other hand, if you understand the concepts in this book, along with the details of programming in C++, you will have all the tools you need to do well on the exam. What is a programming language? The programming language you will be learning is C++, because that is the language the AP exam is based on, as of 1998. Before that, the exam used Pascal. Both C++ and Pascal are high-level languages; other high-level languages you might have heard of are Java, C and FORTRAN.

9 As you might infer from the name high-level language, there are also low-level languages, sometimes referred to as machine language or assembly language. Loosely-speaking, computers can only execute programs written in low-level languages. Thus, programs written in a high-level language have to be translated before they can run. This translation takes some time, which is a 1. 2 CHAPTER 1. THE WAY OF THE PROGRAM. small disadvantage of high-level languages. But the advantages are enormous. First, it is much easier to program in a high-level language; by easier I mean that the program takes less time to write, it's shorter and easier to read, and it's more likely to be correct. Secondly, high-level languages are portable, meaning that they can run on different kinds of computers with few or no modifications. Low-level programs can only run on one kind of computer, and have to be rewritten to run on another.

10 Due to these advantages, almost all programs are written in high-level lan- guages. Low-level languages are only used for a few special applications. There are two ways to translate a program; interpreting or compiling. An interpreter is a program that reads a high-level program and does what it says. In effect, it translates the program line-by-line, alternately reading lines and carrying out commands. source code interpreter The interpreter .. and the result reads the appears on source the screen. A compiler is a program that reads a high-level program and translates it all at once, before executing any of the commands. Often you compile the program as a separate step, and then execute the compiled code later. In this case, the high-level program is called the source code, and the translated program is called the object code or the executable. As an example, suppose you write a program in C++.