Preface

This text is intended for a complete course in programming and problem solving. The book covers the material of typical Computer Science 1 and Computer Science 2 courses at the undergraduate level, but it is intended for the high school audience. The book is Advanced Placement (AP)-compliant for the A and AB levels, covering all of the required subset of Java™ for both levels.

We present six major aspects of computing, some in stand-alone chapters and others spread across several chapters:

1. Programming Basics. This deals with the basic ideas of problem solving with computers, including primitive data types, control structures, methods, algorithm development, and complexity analysis.

2. Object-Oriented Programming. OOP is today’s dominant programming paradigm. All the essentials of this subject are covered.

3. Data and Information Processing. Fundamental data structures are discussed. These include strings, arrays, files, lists, stacks, queues, trees, sets, and maps. The general concept of abstract data type is introduced, and the difference between abstraction and implementation is illustrated. Complexity analysis is used to evaluate space/time tradeoffs of different implementations of ADTs.

4. Software Development Life Cycle. Rather than isolate software development techniques in one or two chapters, the book deals with them throughout in the context of numerous case studies.

5. Graphical User Interfaces and Event-Driven Programming. Many books at this level restrict themselves to character-based terminal I/O. The reason is simple. Graphical user interfaces and event-driven programming usually are considered too complex for beginning students. In this book, we circumvent the complexity barrier and show how to develop programs with graphical user interfaces with almost the same ease as their terminal-based counterparts.

7. Web Basics. The programming of Web pages with HTML and applets is introduced.

Focus on Fundamental Computer Science Topics

There seem to be two types of introductory Java textbooks. The first emphasizes basic problem solving and programming techniques, and the second emphasizes language features. This book takes the former approach and introduces Java features as they are needed to support programming concepts. In this way, all the AP-required syntax is covered without allowing the book to be syntax driven. Some additional and more advanced Java features, not part of the AP requirement, are covered in end-of-chapter sections and in the appendices.

Methods and Objects, Early or Late?

Occasionally, people argue about whether methods and objects should be introduced early or late in the first course. In Java, even the simplest program involves both, so the problem really becomes one of how to introduce these concepts in a clear and meaningful manner from the outset. Starting with the first program, we show how to instantiate and send messages to objects. The book’s early chapters (2 through 4) focus on the use of objects, arithmetic expressions, control constructs, and algorithms in the context of short, simple programs. As programs become more complex, it becomes advantageous to decompose them into cooperating components. With this end in mind, Chapter 5 shows how to develop systems of cooperating classes and methods. Thus, we take a pragmatic rather than an ideological approach to the question of when to introduce methods and objects with complete confidence that students will master both by the end of the course.

Revisiting Control Structures, Classes, and Arrays

Years of teaching experience have demonstrated that beginning programming students have the most difficulty with control structures, classes, and arrays. In this text, we have sought to soften the blow by introducing these ideas in two steps. First, a chapter gives an initial overview of a topic using the most basic features in simple but realistic applications. A follow-up chapter then revisits the topic to fill in and refine the details.

Two Approaches to Data Structures

There are two approaches usually taken to data structures, that of the client who uses them and that of the implementer who writes their code. Courses that emphasize the first approach tend to be application oriented. Modern languages such as Java tend to support this approach well by providing a large set of classes for such data structures as lists and sets. However, some data structures, for example, queues and binary search trees, are not provided, so instructors must provide add-ons or require students to implement them. Over the past few years, the AP testing association has taken this approach, providing the so-called “AP classes” when necessary.

Courses that emphasize data structure implementation tend to use it as a vehicle for discussing space/time complexity tradeoffs and as an entry point for examining broad concepts such as memory management and algorithm design. Unfortunately, students who are expected to implement a list interface with arrays, linked structures, and iterators are likely to get bogged down in hundreds of lines of code and never see an application.

This text straddles both of these approaches to data structures. We provide introductory chapters on the interfaces and applications of each data structure and then follow-up chapters on implementations. Moreover, each implementation is presented as a prototype or trimmed-down version that allows students to explore its essential features and the space/time trade-offs without getting bogged down in details.

New in This Edition

The Advanced Placement test now requires an understanding of certain new features available in Java 5.0. From the AP perspective, the most important new feature in Java 5.0 is the generic collection. A generic collection requires the programmer to specify the collection’s element type. AP A level students must know how to use the generic array list collection. They must also know how to use an enhanced for loop with arrays and array lists. The material on arrays, array lists and for loops has been updated to reflect these changes in requirements.

The AP AB level students must also know how to use the generic versions of lists, sets, maps, stacks, queues, priority queues, and iterators. The material in Chapters 13 through 19, which covers the AP AB requirements, has been thoroughly revised to adhere to the new standard. We also show how to define new classes that implement generic collections, such as stacks, queues, binary search trees, and heaps.

As in previous years, the AP test requires simple standard terminal output but no input. A realistic first course will need some form of input, if only from the keyboard. Java 5.0 includes a delightful new Scanner class for text input from the keyboard and from files. Also included are methods for formatting text for output. The new edition of the book now uses these new features instead of an open source toolkit for text I/O.

In response to the suggestions of some instructors, we have moved the material on graphics and GUIs, which is not required for the AP test, to end-of-chapter sections. The introduction of this extra material is gradual enough that we have been able to dispense with the use of an open source toolkit and rely on the standard Java toolkits in the new edition. Instructors are now free to view graphics and GUIs as extra material to challenge students, and will not have to install or teach non-standard toolkits to accomplish this.

However, one non-standard toolkit, a TurtleGraphics package, has proven to be so popular with instructors and students that we have retained it in a late chapter to illustrate some advanced concepts. As usual, this toolkit is available on the instructor resource CD and from the Web site http://www.wlu.edu/~lambertk/hsjava/. The Web site is the preferred source because it contains the latest release of TurtleGraphics together with online documentation and other related materials. An online tutorial that introduces the use of TurtleGraphics is also available from the Web site.

Because of these changes, there is now no need to retain the extra unit of chapters on material such as graphics, file processing, the Web, and GUIs from the previous edition. The chapter on the Web and applets has been move up so it can be examined earlier in the course; the material on file processing has been moved to an appendix.

Case Studies, the Software Life Cycle, and Comments

The book contains numerous case studies. These are complete Java programs ranging from the simple to the substantial. To emphasize the importance and usefulness of the software development life cycle, case studies are presented in the framework of a user request followed by analysis, design, and implementation, with well-defined tasks performed at each stage. Some case studies are carried through several chapters or extended in end-of-chapter programming projects.

Programming consists of more than just writing code, so we encourage students to submit an analysis and design as part of major programming assignments. We also believe that code should be properly commented, and for purposes of illustration, we include comments in selected examples of the code in the book.

Exercises

The book contains several different types of exercises. Most sections end with exercise questions that reinforce the reading by asking basic questions about the material in the section. Each chapter ends with a set of review exercises. All chapters except the first one include programming projects of varying degrees of difficulty. Finally, each chapter has a critical thinking activity that allows the student to reflect on a major topic covered in the chapter.

Special Features

Scattered throughout the book are short essays called Notes of Interest. These present historical and social aspects of computing, including computer ethics and security.

We Appreciate Your Feedback

The AP A-level material is covered in the first 12 chapters of the book. The AB-only material is covered in Chapters 13 through 19. Chapter 8 covers material not included in the AP course requirements.

We have tried to produce a high-quality text, but should you encounter any errors, please report them to klambert@wlu.edu. A listing of errata, should they exist, and other information about the book will be posted on the Web site http://www.wlu.edu/~lambertk/hsjava/.

Kenneth A. Lambert

Lexington, VA

Martin Osborne

Bellingham, Washington