The Fractal applet at right uses recursion and Logo-like commands from the Turtle class in Chapter One; a random-number generator makes a different 2000+ leaf tree on each reload.
This copyrighted material is free of charge for individual use. PDF files for easy printing or reading over the internet are here , as well as source code for the program listings. However, people who want to use this textbook to teach a class are to fill out the 5-minute questionaire at the end of this webpage and email it to me. I will always respond by giving permission to use the textbook free of charge in that class. Note: This textbook has been carefully copy-edited, but the artwork has not been drawn by a professional.
The main objective of this book for CS1 and CS2 is to introduce object-oriented software design at the very beginning, so it can be developed slowly and thoroughly. We do this in the context of a large number of realistic software packages. From the first week, students begin to develop a feel for what it is like to be a practicing computer scientist.
A primary goal for the first third of a semester CS1 course should be that students learn to write realistic and useful object-oriented programs with at least the following two levels of coding, using only the Sun standard library:
Most textbooks work bottom-up to this milestone, beginning with numeric types and operations. Control structures and expressions are introduced and illustrated in this numeric context. Examples in the first half of such a textbook are usually small, self-contained, unrealistic main methods. This textbook by contrast works top-down to this milestone -- objects first, beginning in the first ten pages.
We start with object design: The analysis of a problem leads to deciding what objects we will need, what actions they can take and what queries they can answer, so we can accomplish the given task. In other words, object design is choosing the public methods that the objects need to have and deciding how they will be used. Once we have settled those questions, we can think about how to implement the objects, i.e., what their private instance variables are and how we code the methods.
Chapter One is a preliminary overview chapter. Chapters Two and Three concentrate on object design using primarily instance methods and inheritance. The conditions for ifs and whiles are entirely in terms of method calls by objects, not numeric expressions. Chapter Four introduces instance variables for the implementation of objects, thereby allowing stand-alone programs with no book-supplied classes that hide implementation details. Chapter Five introduces class variables.
The Table of Contents is at this link. It is a PDF file (needing Adobe), as are the files linked from the rest of this webpage. Note that all material needed for the AP CS exams, both A and AB, is in this book.
Chapter One outlines basic algorithm design techniques that are illustrated multiple times in every chapter thereafter. It presents a Logo-like context in which students can write, compile and execute small but interesting graphics application programs in the first week of class. Experience has shown that students enjoy applying these method calls without feeling a strong need to first see the underlying implementation of the Java commands that move the Turtle, just as Java programmers use Graphics methods without feeling a strong need to see Sun's underlying coding for them. The complete implementation of the Turtle class is developed later in this book; for now, students create and use Turtles without dealing directly with JApplet or JFrame at all. Look at Listings 1.5 and 1.6 to see how the main method and subclasses are used.
Chapter Two describes basic method calls for one particular context we call Vic objects. A Vic object is a fixed-length sequence of elements that can be shifted around. It represents a component of a small electronic appliance. Students learn to develop various small application programs using Vic objects and, for more complex logics, to develop subclasses of Vic containing instance methods called by a main method. The if and if-else statements are introduced for use in such methods, so that the actions taken are method calls that modify the state of an object and the conditional tests are method calls that query the state of an object. This contrasts with the usual numeric context, where the examples of if-statements test conditions of numeric inequality and perform actions that read/compute/write numbers. In the Vic context, the input is the initial state of the objects and the output is the final state of the objects. Look at Listings 2.8 and 2.9 to see how boolean variables and boolean operators are gradually introduced.
Chapter Three continues with the Vic context. Parameters and while-statements are introduced for situations where an object repeats an action until a certain condition becomes true. This makes the programming problems complex enough to justify a thorough discussion of the five-step object-oriented paradigm for the analysis, design, and implementation of software that was introduced in Chapter One and illustrated several times since then. Note that it is not appropriate to introduce the student to all three looping statements in Chapter Three; for-statements are generally for situations where a counter is incremented, and such situations do not even arise in this book until Chapter Four. An advantage of this is that students find loops easier to understand when the full range of possibilities is postponed for a bit. Look at Listing 3.4 to see how clear while-loops can be when numbers are not involved.
Chapter Four introduces instance variables and input/output in a game-program context, which finishes the top-down presentation of the development of stand-alone programs. Thus students reach this first milestone, the development of realistic object-oriented programs using only the Java Sun library, by the end of the fourth week of a regular semester. And they make the journey while immersed in totally object-oriented contexts. Look at Listing 4.6 to see the game of guessing a number 1 to 100 as a subclass of a BasicGame (which is in Listing 4.3).
Students find the concept of inheritance quite natural when they only have instance methods without instance variables. This avoids the alternatives of either a long complex main method or several shorter class methods, neither of which feels natural in Java. After three chapters of using simple inheritance, students are ready for inheritance with polymorphism in Chapter Four, which is necessary for an honest presentation of applets (otherwise how do you explain why writing a method heading as public void paint(Graphics2D page) causes a blank drawing area?). Additional extended examples using inheritance are implemented in Chapters 5, 7, 11, 14, 15, 16, 18, and 19.
Chapter Five completes the basic object-oriented language features with a discussion of class methods, class variables, and final variables. It includes an implementation of a Vic simulation using Strings, and finishes with an extended case study on networks. Chapter Five also introduces recursion (though it can be postponed for a while, since recursion is not used again until Chapters Thirteen, Fourteen, and later).
Chapter Six covers basic language features used throughout the rest of the book: double, long, and char types; more String methods; and additional Sun library input/output methods. It ends with a Model/View/Controller case study.
Chapter Seven thoroughly discusses one-dimensional arrays in the context of a personnel database. It includes sequential search, the insertion sort, and an introduction to two-dimensional arrays. Every chapter thereafter illustrates the use of arrays in a different context to solve different problems. However, some instructors prefer to delay arrays until later in the course. To facilitate this, the first part of each of Chapters Eight through Eleven does not use arrays; simply postpone Sections 8.7-8.10, 9.9-9.11, 10.6-10.8, and 11.7-11.8 for a while. Arrays are used heavily beginning in Chapter Twelve.
The first seven chapters cover the basic Java language features, for which the software packages they discuss are a thin veneer. The only additional Java language features used in more than one chapter of this book are in Sections 9.1-9.3 (exceptions, throw, try/catch) and 11.1-11.3 (interfaces, abstract classes, instanceof). Consequently, Chapters Twelve and later are independent of each other and of Chapters Eight and Ten, though roughly in increasing order of difficulty. However, it would be best to cover 14.1-14.3 (easy introduction to linked lists) before covering chapters after Chapter Fourteen.
The remaining chapters emphasize analysis and design more heavily. Each discusses the process for developing a different software package, illustrating a reasonable approach to the construction of small to medium software suites as well as the new language concepts of that chapter. Most of these later chapters begin with a one or two-page analysis of the new software situation and a partial object design to motivate the material in the chapter. Although these realistic software situations were shaped to the language needs at that point, a primary purpose is to deepen the students' understanding of software analysis, design, and implementation. A two-semester sequence can omit the major part of several of these applications if desired.
Chapter Eight describes graphics methods and applets. It is not needed for the rest of the book. The essential material of Sections 8.1-8.3 are accessible directly after Section 4.5. However, if your primary purpose is simply to let students enjoy graphical programming early, the Logo-like Turtle application programs in Chapter One should suffice (Turtles provide their own JFrame so students do not deal with those complexities so early).
Chapter Nine discusses the throwing and catching of Exceptions. The first three sections of this chapter contain all the new language features for the rest of the book. They include elementary text file input, since that is the most common use of checked Exceptions. These first three sections are accessible directly after Section 6.5.
Chapter Ten introduces event-handling and frames. This is accessible directly after Section 4.7 and independent of the material on applets. The only new Java language feature is inner classes, which are not used elsewhere in the book. Listing 10.5 in particular provides a simple template for GUIs. The MVC pattern used for the case study of Chapter Six is used again for this chapter's case study.
Chapter Eleven describes and illustrates the use of interfaces and abstract classes. The case study develops subclasses of an abstract Numeric class: one to represent fractions, one to represent complex numbers, and one to represent integers up to 54 digits long. The first four sections of this chapter contain all the new language features for the rest of the book, including a discussion of the Double and Integer classes.
Chapter Twelve goes deeply into file input and output and gives substantial practice with multidimensional arrays. Both topics are used in the case study.
Chapter Thirteen presents the selection sort, the insertion sort, two N*log(N) sorting methods, and several others, all in the context of an array of Comparable objects. It can be covered directly after Chapter Seven.
Chapter Fourteen is an introduction to the use of linked lists to implement stacks and queues. An array implementation is given first so that students can compare the two kinds of implementation, followed by a parallel linked list implementation. This and later chapters discuss standard CS 2 data structures and algorithms: Collections, Iterators, Maps, hashtables, binary search trees, priority queues, heaps, graphs, and minimal spanning trees.
Appendices include a summary of good style principles, a glossary of terms indexed with page references, and loads of major programming projects.
· Appendices include a summary of the programming style principles scattered through the book, a glossary of terms indexed by page, an alphabetical list of common compile-time errors with a translation into student terms of what they really mean, an indexed overview-tree of the 130-some Sun library classes along with their methods described in the book (showing superclasses and packages), and about 140 major programming project assignments organized by chapter.
· Several concepts that computer science majors can expect to see in advanced courses are discussed on an introductory level. For instance, a deceptively simple trio of classes for nodes in a network is developed in a case study in Chapter Five; recursion leads to a solution of the Traveling Salesman Problem.
· Each section that introduces new Java language elements ends with a box giving a formal summary of the syntax and semantics. Each chapter starts with an overview and ends with a thorough review that includes all new language features, all new Sun library methods, and all definitions of essential vocabulary items introduced in the chapter. Also, Chapter Five ends with a complete review of all Java language features and Sun library methods up to that point.
· The last section or two of most chapters gives a brief description and illustration of additional Sun library methods and classes not used elsewhere in the book. These are sufficiently similar to methods and classes covered thoroughly in the normal text that they do not need an extended discussion. Isolating the less crucial Sun library classes this way makes them available for use in major projects or as a reference in later courses while reducing the burden on students' memories. These sections are starred to indicate they are not included in chapter reviews.
· A clear and well-structured method for analysis and design of software is introduced in Chapter One and used several times in every chapter. It emphasizes designing in English before writing in Java.
· All material needed for the AP CS A exam is in Chapters 1-7 plus Sections 9.1-9.3, 11.1-11.4, and 13.1-13.6. All of the additional AB exam material is in Chapters 14-18. Very little in the way of non-AP language features is used in the book (e.g., char is limited to Chapter Six; do/while, switch, and protected are limited to just 1 or 2 sections). However, ?: is used regularly.
· UML is introduced in Chapter Two and used several times in every later chapter except Thirteen (which discusses sorting algorithms rather than object classes). It is consistent with the representation of relationships among classes used by BlueJ (which is described at the end of Chapter Four).
· Javadoc-conformant documentation is introduced in Chapter Two and used consistently thereafter.
Sequencing: Each chapter is divided into parts A and B. Only Part A is required to go further in the book; Part B is for reinforcement and enrichment. The first 14 chapters have the following dependencies, except that Part A of Chapter 7 (Sections 7.1-7.6 on arrays) is also required for every chapter from Chapter 12 on. Each of Chapters 15, 16, and 17 require only Part A of Chapters 1-7, 9, 11, and 14.
1A -> 2A -> 3A -> 4A ----> 5A ----> 6A ----> 7A -----> 13A
|--> 8A |--> 9A -----> 12A
|--> 10A |--> 11A ----> 14A
This text has been classroom-tested both in a first course in programming and in a course for students who have previously had a different programming language. All of the new language features are covered in Part A, with the bulk of the examples of software design in the latter part of the chapter. This means that beginning students see definitions early in the chapter with shorter examples and then see extended examples reinforcing the concepts and language features again later in the chapter. And it means that a course for students who have substantial previous programming experience can cover all of the language material much more rapidly, specifically, Part A of Chapters 1-7, 9, and 11 (174 pages in all). The rest of each of those chapters can be skipped or left for these experienced students to read on their own.
This textbook can be used in ways other than the primary text. For example, if you love Karel the Robot but want a book that will carry forward with object-oriented development, teach Karel for a number of weeks and then start this text at Chapter Four or Five or Six (depending on how far you get in the Karel material). Or if your textbook delays object-oriented material too long, you may wish to supplement it with Chapters Two through Five. Or if your textbook does not give as much drill on array algorithms as you think best, add Chapter Seven, emphasizing Sections 7.6 and 7.7.
Future Editions: This third edition came out March 2003. I do not expect to make more changes until March 2004, though I will post errata as they arise. FYI: I published a CS 1 textbook and a CS 2 textbook with Harper and Row in the 1980s. On-line publishing is more satisfying than print.
If you want to use this textbook in a class or with any other group of people, either as the main text or as a supplement, paste the following seven questions into an email to firstname.lastname@example.org and fill in the answers. You will receive permission by return mail. There is no charge for using the book in a class; I just need to know who is using it. I will also send an instructor's manual to you within a week or so.
1. Your name and email address: ____
2. Name of school, city/state/country: ____
3. Nature of the class (e.g., University CS1, H.S. AP) : ____
you expect to use it: from date ________
to date ________
5. Estimated number of students: ____
6. Which chapters do you expect your students to use: ___
7. Check one of the
following: Will you use it as
(a) the primary and required text. ___
(b) a required supplement. ___
(c) a suggested supplement. ___
Copyright (c)2001 - Dr. William C. Jones, Jr.