Think Java: How To Think Like A Computer Scientist
Think JavaHow to Think Like a Computer ScientistAllen B. Downey5.1.2
Copyright 2012 Allen Downey.Permission is granted to copy, distribute, transmit and adapt this work undera Creative Commons Attribution-NonCommercial-ShareAlike 3.0 UnportedLicense: f you are interested in distributing a commercial version of this work, pleasecontact Allen B. Downey.The original form of this book is LATEX source code. Compiling this LATEXsource has the effect of generating a device-independent representation of thebook, which can be converted to other formats and printed.The LATEX source for this book is available from: http://thinkapjava.comThis book was typeset using LATEX. The illustrations were drawn in xfig. Allof these are free, open-source programs.
Preface“As we enjoy great Advantages from the Inventions of others, weshould be glad of an Opportunity to serve others by any Inventionof ours, and this we should do freely and generously.”—Benjamin Franklin, quoted in Benjamin Franklin by EdmundS. Morgan.Why I wrote this bookThis is the fifth edition of a book I started writing in 1999, when I wasteaching at Colby College. I had taught an introductory computer scienceclass using the Java programming language, but I had not found a textbookI was happy with. For one thing, they were all too big! There was no way mystudents would read 800 pages of dense, technical material, even if I wantedthem to. And I didn’t want them to. Most of the material was too specific—details about Java and its libraries that would be obsolete by the end of thesemester, and that obscured the material I really wanted to get to.The other problem I found was that the introduction to object-oriented programming was too abrupt. Many students who were otherwise doing welljust hit a wall when we got to objects, whether we did it at the beginning,middle or end.So I started writing. I wrote a chapter a day for 13 days, and on the 14thday I edited. Then I sent it to be photocopied and bound. When I handed itout on the first day of class, I told the students that they would be expectedto read one chapter a week. In other words, they would read it seven timesslower than I wrote it.
ivChapter 0. PrefaceThe philosophy behind itHere are some of the ideas that make the book the way it is: Vocabulary is important. Students need to be able to talk about programs and understand what I am saying. I try to introduce the minimum number of terms, to define them carefully when they are firstused, and to organize them in glossaries at the end of each chapter.In my class, I include vocabulary questions on quizzes and exams, andrequire students to use appropriate terms in short-answer responses. To write a program, students have to understand the algorithm, knowthe programming language, and they have to be able to debug. I thinktoo many books neglect debugging. This book includes an appendix ondebugging and an appendix on program development (which can helpavoid debugging). I recommend that students read this material earlyand come back to it often. Some concepts take time to sink in. Some of the more difficult ideas inthe book, like recursion, appear several times. By coming back to theseideas, I am trying to give students a chance to review and reinforce or,if they missed it the first time, a chance to catch up. I try to use the minimum amount of Java to get the maximum amountof programming power. The purpose of this book is to teach programming and some introductory ideas from computer science, not Java. Ileft out some language features, like the switch statement, that areunnecessary, and avoided most of the libraries, especially the ones likethe AWT that have been changing quickly or are likely to be replaced.The minimalism of my approach has some advantages. Each chapter is aboutten pages, not including the exercises. In my classes I ask students to readeach chapter before we discuss it, and I have found that they are willing todo that and their comprehension is good. Their preparation makes class timeavailable for discussion of the more abstract material, in-class exercises, andadditional topics that aren’t in the book.But minimalism has some disadvantages. There is not much here that isintrinsically fun. Most of my examples demonstrate the most basic use ofa language feature, and many of the exercises involve string manipulation
vand mathematical ideas. I think some of them are fun, but many of thethings that excite students about computer science, like graphics, sound andnetwork applications, are given short shrift.The problem is that many of the more exciting features involve lots of detailsand not much concept. Pedagogically, that means a lot of effort for not muchpayoff. So there is a tradeoff between the material that students enjoy andthe material that is most intellectually rich. I leave it to individual teachersto find the balance that is best for their classes. To help, the book includesappendices that cover graphics, keyboard input and file input.Object-oriented programmingSome books introduce objects immediately; others warm up with a moreprocedural style and develop object-oriented style more gradually. This bookuses the “objects late” approach.Many of Java’s object-oriented features are motivated by problems with previous languages, and their implementations are influenced by this history.Some of these features are hard to explain if students aren’t familiar withthe problems they solve.It wasn’t my intention to postpone object-oriented programming. On thecontrary, I got to it as quickly as I could, limited by my intention to introduceconcepts one at a time, as clearly as possible, in a way that allows studentsto practice each idea in isolation before adding the next. But I have to admitthat it takes some time to get there.The Computer Science AP ExamNaturally, when the College Board announced that the AP Exam wouldswitch to Java, I made plans to update the Java version of the book. Lookingat the proposed AP Syllabus, I saw that their subset of Java was all butidentical to the subset I had chosen.During January 2003, I worked on the Fourth Edition of the book, makingthese changes: I added sections to improve coverage of the AP syllabus.
viChapter 0. Preface I improved the appendices on debugging and program development. I collected the exercises, quizzes, and exam questions I had used inmy classes and put them at the end of the appropriate chapters. Ialso made up some problems that are intended to help with AP Exampreparation.Finally, in August 2011 I wrote the fifth edition, adding coverage of theGridWorld Case Study that is part of the AP Exam.Free books!Since the beginning, this book has under a license that allows users to copy,distribute and modify the book. Readers can download the book in a varietyof formats and read it on screen or print it. Teachers are free to print asmany copies as they need. And anyone is free to customize the book fortheir needs.People have translated the book into other computer languages (includingPython and Eiffel), and other natural languages (including Spanish, Frenchand German). Many of these derivatives are also available under free licenses.Motivated by Open Source Software, I adopted the philosophy of releasingthe book early and updating it often. I do my best to minimize the numberof errors, but I also depend on readers to help out.The response has been great. I get messages almost every day from peoplewho have read the book and liked it enough to take the trouble to send ina “bug report.” Often I can correct an error and post an updated versionwithin a few minutes. I think of the book as a work in progress, improving alittle whenever I have time to make a revision, or when readers send feedback.Oh, the titleI get a lot of grief about the title of the book. Not everyone understandsthat it is—mostly—a joke. Reading this book will probably not make youthink like a computer scientist. That takes time, experience, and probably afew more classes.
viiBut there is a kernel of truth in the title: this book is not about Java, andit is only partly about programming. If it is successful, this book is about away of thinking. Computer scientists have an approach to problem-solving,and a way of crafting solutions, that is unique, versatile and powerful. I hopethat this book gives you a sense of what that approach is, and that at somepoint you will find yourself thinking like a computer scientist.Allen DowneyNeedham, MassachusettsJuly 13, 2011Contributors ListWhen I started writing free books, it didn’t occur to me to keep a contributors list. When Jeff Elkner suggested it, it seemed so obvious that I amembarassed by the omission. This list starts with the 4th Edition, so it omitsmany people who contributed suggestions and corrections to earlier versions.If you have additional comments, please send them to:feedback@greenteapress.com Ellen Hildreth used this book to teach Data Structures at WellesleyCollege, and she gave me a whole stack of corrections, along with somegreat suggestions. Tania Passfield pointed out that the glossary of Chapter 4 has someleftover terms that no longer appear in the text. Elizabeth Wiethoff noticed that my series expansion of exp( x2 ) waswrong. She is also working on a Ruby version of the book! Matt Crawford sent in a whole patch file full of corrections! Chi-Yu Li pointed out a typo and an error in one of the code examples. Doan Thanh Nam corrected an example in Chapter 3. Stijn Debrouwere found a math typo.
viiiChapter 0. Preface Muhammad Saied translated the book into Arabic, and found severalerrors. Marius Margowski found an inconsistency in a code example. Guy Driesen found several typos. Leslie Klein discovered yet another error in the series expansion ofexp( x2 ), identified typos in the card array figures, and gave helpfulsuggestions to clarify several exercises.Finally, I wish to acknowledge Chris Mayfield for his significant contributionto version 5.1 of this book. His careful review lead to over one hundredcorrections and improvements throughout. Several new features include embedded hypertext links and cross references, consistent layout of all exercises,and Java syntax highlighting in code examples.
ContentsPrefaceiii1 The way of the program11.1What is a programming language? . . . . . . . . . . . . . . .11.2What is a program? . . . . . . . . . . . . . . . . . . . . . . .31.3What is debugging? . . . . . . . . . . . . . . . . . . . . . . .41.4Formal and natural languages . . . . . . . . . . . . . . . . .61.5The first program . . . . . . . . . . . . . . . . . . . . . . . .81.6Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.7Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Variables and types132.1More printing . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.4Printing variables . . . . . . . . . . . . . . . . . . . . . . . . 162.5Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.6Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
xContents2.7Order of operations . . . . . . . . . . . . . . . . . . . . . . . 192.8Operators for Strings . . . . . . . . . . . . . . . . . . . . . 202.9Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.10Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.11Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Void methods253.1Floating-point . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2Converting from double to int . . . . . . . . . . . . . . . . 263.3Math methods . . . . . . . . . . . . . . . . . . . . . . . . . . 273.4Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.5Adding new methods . . . . . . . . . . . . . . . . . . . . . . 293.6Classes and methods . . . . . . . . . . . . . . . . . . . . . . 313.7Programs with multiple methods . . . . . . . . . . . . . . . . 323.8Parameters and arguments . . . . . . . . . . . . . . . . . . . 333.9Stack diagrams . . . . . . . . . . . . . . . . . . . . . . . . . 343.10Methods with multiple parameters . . . . . . . . . . . . . . . 353.11Methods that return values . . . . . . . . . . . . . . . . . . . 363.12Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.13Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 Conditionals and recursion394.1The modulus operator . . . . . . . . . . . . . . . . . . . . . 394.2Conditional execution . . . . . . . . . . . . . . . . . . . . . . 394.3Alternative execution . . . . . . . . . . . . . . . . . . . . . . 40
Contentsxi4.4Chained conditionals . . . . . . . . . . . . . . . . . . . . . . 414.5Nested conditionals . . . . . . . . . . . . . . . . . . . . . . . 424.6The return statement . . . . . . . . . . . . . . . . . . . . . . 434.7Type conversion . . . . . . . . . . . . . . . . . . . . . . . . . 434.8Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.9Stack diagrams for recursive methods . . . . . . . . . . . . . 464.10Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.11Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 GridWorld: Part 1515.1Getting started . . . . . . . . . . . . . . . . . . . . . . . . . 515.2BugRunner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.3Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536 Value methods556.1Return values . . . . . . . . . . . . . . . . . . . . . . . . . . 556.2Program development . . . . . . . . . . . . . . . . . . . . . . 576.3Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.4Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.5Boolean expressions . . . . . . . . . . . . . . . . . . . . . . . 616.6Logical operators . . . . . . . . . . . . . . . . . . . . . . . . 626.7Boolean methods . . . . . . . . . . . . . . . . . . . . . . . . 636.8More recursion . . . . . . . . . . . . . . . . . . . . . . . . . . 646.9Leap of faith . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.10One more example . . . . . . . . . . . . . . . . . . . . . . . 676.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.12Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
xiiContents7 Iteration and loops757.1Multiple assignment . . . . . . . . . . . . . . . . . . . . . . . 757.2The while statement . . . . . . . . . . . . . . . . . . . . . . 767.3Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787.4Two-dimensional tables . . . . . . . . . . . . . . . . . . . . . 807.5Encapsulation and generalization . . . . . . . . . . . . . . . 817.6Methods and encapsulation . . . . . . . . . . . . . . . . . . . 827.7Local variables . . . . . . . . . . . . . . . . . . . . . . . . . . 837.8More generalization . . . . . . . . . . . . . . . . . . . . . . . 847.9Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 878 Strings and things918.1Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918.2Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928.3Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938.4Run-time errors . . . . . . . . . . . . . . . . . . . . . . . . . 938.5Reading documentation . . . . . . . . . . . . . . . . . . . . . 958.6The indexOf method . . . . . . . . . . . . . . . . . . . . . . 958.7Looping and counting . . . . . . . . . . . . . . . . . . . . . . 968.8Increment and decrement operators . . . . . . . . . . . . . . 978.9Strings are immutable . . . . . . . . . . . . . . . . . . . . . 988.10Strings are incomparable . . . . . . . . . . . . . . . . . . . 988.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 998.12Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Contentsxiii9 Mutable objects1079.1Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079.2Point objects . . . . . . . . . . . . . . . . . . . . . . . . . . 1089.3Instance variables . . . . . . . . . . . . . . . . . . . . . . . . 1099.4Objects as parameters . . . . . . . . . . . . . . . . . . . . . 1109.5Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109.6Objects as return types . . . . . . . . . . . . . . . . . . . . . 1119.7Objects are mutable . . . . . . . . . . . . . . . . . . . . . . . 1119.8Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1129.9null . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1149.10Garbage collection9.11Objects and primitives . . . . . . . . . . . . . . . . . . . . . 1159.12Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1169.13Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117. . . . . . . . . . . . . . . . . . . . . . . 11410 GridWorld: Part 212310.1Termites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12510.2Langton’s Termite . . . . . . . . . . . . . . . . . . . . . . . . 12810.3Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12911 Create your own objects13111.1Class definitions and object types . . . . . . . . . . . . . . . 13111.2Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13211.3Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . 13311.4More constructors . . . . . . . . . . . . . . . . . . . . . . . . 134
xivContents11.5Creating a new object. . . . . . . . . . . . . . . . . . . . . 13511.6Printing objects . . . . . . . . . . . . . . . . . . . . . . . . . 13611.7Operations on objects . . . . . . . . . . . . . . . . . . . . . . 13711.8Pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . 13711.9Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14011.10 Fill-in methods . . . . . . . . . . . . . . . . . . . . . . . . . 14111.11 Incremental development and planning . . . . . . . . . . . . 14211.12 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . 14311.13 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14411.14 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14411.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14512 Arrays14912.1Accessing elements . . . . . . . . . . . . . . . . . . . . . . . 15012.2Copying arrays . . . . . . . . . . . . . . . . . . . . . . . . . 15112.3Arrays and objects . . . . . . . . . . . . . . . . . . . . . . . 15112.4for loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15212.5Array length . . . . . . . . . . . . . . . . . . . . . . . . . . . 15312.6Random numbers . . . . . . . . . . . . . . . . . . . . . . . . 15312.7Array of random numbers . . . . . . . . . . . . . . . . . . . 15412.8Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15512.9The histogram . . . . . . . . . . . . . . . . . . . . . . . . . . 15712.10 A single-pass solution . . . . . . . . . . . . . . . . . . . . . . 15712.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15812.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Contentsxv13 Arrays of Objects16513.1The Road Ahead . . . . . . . . . . . . . . . . . . . . . . . . 16513.2Card objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 16513.3The printCard method . . . . . . . . . . . . . . . . . . . . . 16713.4The sameCard method . . . . . . . . . . . . . . . . . . . . . 16913.5The compareCard method . . . . . . . . . . . . . . . . . . . 17013.6Arrays of cards . . . . . . . . . . . . . . . . . . . . . . . . . 17113.7The printDeck method . . . . . . . . . . . . . . . . . . . . . 17313.8Searching13.9Decks and subdecks . . . . . .
I think too many books neglect debugging. This book includes an appendix on debugging and an appendix on program development (which can help avoid debugging). I recommend that students read this material early and come back to it often. Some concepts take time to sink in. Some of the more di cult ideas in the book, like recursion, appear .
java.io Input and output java.lang Language support java.math Arbitrary-precision numbers java.net Networking java.nio "New" (memory-mapped) I/O java.rmi Remote method invocations java.security Security support java.sql Database support java.text Internationalized formatting of text and numbers java.time Dates, time, duration, time zones, etc.
Java Version Java FAQs 2. Java Version 2.1 Used Java Version This is how you find your Java version: Start the Control Panel Java General About. 2.2 Checking Java Version Check Java version on https://www.java.com/de/download/installed.jsp. 2.3 Switching on Java Console Start Control Panel Java Advanced. The following window appears:
3. _ is a software that interprets Java bytecode. a. Java virtual machine b. Java compiler c. Java debugger d. Java API 4. Which of the following is true? a. Java uses only interpreter b. Java uses only compiler. c. Java uses both interpreter and compiler. d. None of the above. 5. A Java file with
besteht aus der Java-API (Java Application Programming Interface) und der Java-VM (Java Virtual Machine). Abbildung 1: Java-Plattform Die Java-API ist eine große Sammlung von Java-Programmen, die in sog. Pakete (packages) aufgeteilt sind. Pakete sind vergleichbar mit Bibliotheken in anderen Programmiersprachen und umfassen u.a.
JAR Javadoc Java Language jar Security Others Toolkits: FX Java 2D Sound . Java Programming -Week 1. 6/25. Outline Java is. Let’s get started! The JDK The Java Sandbox . into your namespace. java.lang contains the most basic classes in the Java language. It is imported automatically, so
2 Java Applications on Oracle Database 2.1 Database Sessions Imposed on Java Applications 2-1 2.2 Execution Control of Java Applications 2-3 2.3 Java Code, Binaries, and Resources Storage 2-3 2.4 About Java Classes Loaded in the Database 2-4 2.5 Preparing Java Class Methods for Execution 2-5 2.5.1 Compiling Java Classes 2-6
The Java Platform The Java platform has two components: The Java Virtual Machine (Java VM) The Java Application Programming Interface(Java API) The Java API is a large collection of ready-made software components that provide many useful capa
–‘java’ command launches Java runtime with Java bytecode An interpreter executes a program by processing each Java bytecode A just-in-time compiler generates native instructions for a target machine from Java bytecode of a hotspot method 9 Easy and High Performance GPU Programming for Java Programmers Java program (.
