Fundamentals of computer science using Java

Fundamentals of

Computer Science Using Java

David Hughes

JONES AND BARTLETT PUBLISHERS

Fundamentals of

Computer Science

Using Java

David Hughes

Brock University

World Headquarters

Jones and Bartlett Publishers

40 Tall Pine Drive

Sudbury, MA 01776

978-443-5000

[email protected]

www.jbpub.com

Jones and Bartlett Publishers

Canada

2406 Nikanna Road

Mississauga, ON L5C 2W6

CANADA

Jones and Bartlett Publishers

International

Barb House, Barb Mews

London W6 7PA

UK

Copyright © 2002 by Jones and Bartlett Publishers, Inc.

Library of Congress Cataloging-in-Publication Data

Hughes, David (David John Frederick), 1952-

Fundamentals of computer science using Java / David Hughes.

p. cm.

ISBN 0-7637-1761-4

1. Computer science. 2. Java (Computer program language) I. Title.

QA76.H789 2001

005.2'76—dc21 2001029710

8888

All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any

form, electronic or mechanical, including photocopying, recording, or any information storage or retrieval system,

without written permission from the copyright owner.

Chief Executive Officer: Clayton Jones

Chief Operating Officer: Don W. Jones, Jr.

Executive V.P. and Publisher: Robert W. Holland, Jr.

V.P., Design and Production: Anne Spencer

V.P., Manufacturing and Inventory Control: Therese Bräuer

Editor-in-Chief: J. Michael Stranz

Production Manager: Amy Rose

Marketing Manager: Nathan Schultz

Associate Production Editor: Tara McCormick

Editorial Assistant: Theresa DiDonato

Cover Design: Kristin Ohlin

Composition: Northeast Compositors, Inc.

Text Design: Mary McKeon

Printing and Binding: Courier Westford

Cover Printing: John Pow Company, Inc.

This book was typeset in Quark 4.1 on a Macintosh G4. The font families used were Adobe Garamond, Univers, and

Prestige Elite. The first printing was printed on 50# Courier Opaque.

Printed in the United States of America

06 05 04 03 02 10 9 8 7 6 5 4 3 2 1

To my wife Chris, for all those times I was too busy with “the book.”

iii

This page intentionally left blank

Preface

Why this Book

In the summer of 1996, our Computer Science department made the decision to use

Java as the core language for our Computer Science program, beginning that fall.

Although there were many Java books available, we soon discovered that most were

“trade” or “hobby” books, not designed for university courses and certainly not intended

to serve as introductions to Computer Science. It became clear to us that someone

needed to write a “Fundamentals of Computer Science Using Java” book, and I thought,

“why not me?” And now, after years of researching, testing, and writing, I can provide

the book that we searched for years ago: a truly Java-based introduction to Computer

Science.

In a first course in Computer Science, the primary goal is to teach the fundamentals

of the field. Basic concepts are introduced with the help of a programming language

that is often viewed as simply a medium through which algorithms are expressed. From

that perspective, it does not matter which language is used in an introductory course,

because any would suffice. In practice, however, the language can have a profound

impact on the students’ learning experience. First, the style of the language constrains

the way and the order in which topics can be introduced. Further, the language taught

in the first course must support the rest of the curriculum. For these reasons and more,

a language-defined text is an important component in an introductory course.

Object-oriented languages in particular are useful in introductory textbooks and are

certainly appropriate at this time. Having an object-oriented language as the core pro￾gramming language supports many courses at the higher level (e.g., software engineering,

user interfaces, databases). The question is, then, which object-oriented language?

v

Our decision to use Java was based on a number of factors. First, we recognized Java

as a pure object-oriented language, as opposed to C++, which is a hybrid, and thus does

not allow the programmer to fall back into procedural habits. Further, it has a relatively

clear and common syntax that can be understood without having to learn a large class

hierarchy. Finally, Java has compilers available on a great many platforms that are inex￾pensive, not overly resource hungry, and the code is platform-independent. All of these

things make Java ideal for a first university course.

The approach taken in this book is what might best be called an “object-based”

approach. It is my belief that students need to master the skill of method writing before

they can craft meaningful classes. Objects occur right from the start. The student’s code,

however, is written as a client of another class, and thereby makes use of objects through

the delegation model rather than the inheritance model.

The text introduces methods as early as possible and then introduces the control

structures and types necessary for writing methods. When classes are fully introduced,

the students are completely capable of writing the methods for a class and are familiar

with writing one class as a client of another. They soon master writing a class as a sup￾plier. Once classes are available, the text introduces object-oriented software develop￾ment using classes for the decomposition. Responsibility-based design is also introduced

using CRC cards as the design methodology.

The pedagogical approach applied to this text is grounded in the idea that the learn￾ing process can be facilitated through the use of examples. Each new topic is introduced

through a number of complete program examples. Examples are kept as simple as possi￾ble to illustrate important concepts. At the same time, the examples are realistic, and

allow for meaningful use of new constructs. Students can often use the examples as a

starting point for coding of assignment problems.

What is Covered and What is Not

Java, like any programming language, is fairly large and this book does not attempt to

provide complete coverage of all Java topics. As an object-oriented language, Java has

many standard class libraries and many other APIs, and therefore it would not be possi￾ble to provide complete coverage of the language even if I so wished.

The first decision I made was to exclude inheritance. This might seem like heresy,

however, I stand by this decision and believe it is appropriate to exclude inheritance

from an introductory course. In my experience, students have trouble understanding

the true meaning of inheritance, and this often leads them to use inheritance as simply a

mechanism for code borrowing. This is very evident in the structure of many books that

introduce Computer Science in an object-oriented language. In an attempt to make the

first programs interesting, these texts can overuse subclassing. Code reuse through dele￾gation is a much simpler, and often more desirable, approach. In a first course, I prefer

to foster in my students a clear understanding of the basic principles, and I leave inheri￾PREFACE

vi

tance and subclassing for a later course. In our program, inheritance and polymorphism

are introduced in the second year.

One possible objection to excluding inheritance is that without it we cannot write

applets. This is a small loss, as it would be nice if the student’s programs could be

demonstrated using a web browser. The level of programming necessary for writing

applets, however, is really too advanced for an introductory course, since it requires the

use of graphical user interfaces to do anything reasonable. To allow interesting first pro￾grams, the class library TurtleGraphics is used. This class library supports the turtle

graphics model introduced in the programming language Logo.

The AWT and Swing are also not covered in this book. GUI programming requires

an event model for programming that allows apparent non-linear flow of control. This is

confusing for first-year students. Instead, the I/O class library BasicIO is used. This I/O

class library provides a class for prompted input via the dialog box ASCIIPrompter and

provides output to the scrollable window ASCIIDisplayer.

Even though inheritance is not covered, classes definitely are. Classes are the funda￾mental decomposition mechanism in object-oriented design. Of course, without inheri￾tance the design model is incomplete; however, designing with inheritance is difficult

and better learned when a student’s programming skills are more mature.

Exceptions are also a difficult concept for beginning students to grasp because they

introduce a second path of execution. Since Java requires that any exception (other than

RunTimeException) be caught or thrown by the method, code dealing with exceptions

obscures the expression of the algorithm. The most common occurrence of exceptions is

in I/O. To remove the need to deal with exceptions too early, the BasicIO library does

not throw exceptions.

Use of the Book

At Brock, the material presented here forms the substance of a half-year (twelve-week)

course meeting three hours per week. The lectures are supplemented by a one-hour tuto￾rial, which is primarily a question and answer period, and a two-hour laboratory where the

students work on programming assignments. The primary goal of our course is to intro￾duce basic computer science concepts, while introducing language concepts as needed.

Chapter 1 includes a brief history of computing and computing technology, and then

describes the basic hardware and software organization of computer systems. The mate￾rial in Appendix A may be used to supplement this coverage, or can be introduced at a

later time for a clearer understanding of the low-level execution of programs. Chapter 1

also provides a preview to the software development process, and the phases included in

this chapter are repeated in the Case Studies of later chapters.

Chapter 2 begins the coverage of Java. It introduces the Java syntax notation so that

students will be able to read the syntax descriptions that define the language. Turtle

Graphics are used to enhance the early examples. Programs are written as clients of

PREFACE

vii

Turtle objects and make use of simple looping and nesting of loops to produce interest￾ing graphics.

Chapter 3 introduces computations and the basic arithmetic operators of Java. Since

results of computations must be stored, it also introduces variables and assignment.

Chapter 4 covers methods as a mechanism for procedural abstraction. It covers simple

methods, method invocation, parameter passing, and method results, as well as scope

issues.

Chapter 5 covers I/O, specifically the BasicIO package. It describes streams as an

abstraction of I/O and covers input and output streams and output formatting. The

stream concept is consistent with the java.io package, and so many of these concepts are

transferable.

Chapter 6 introduces control structures. Some control structures have already been

used in their simplest form, but here they are described in detail. The chapter spends its

time on the important structures, while only mentioning the less frequently used struc￾tures.

Chapter 7 covers the boolean and char types and emphasizes the difference between

primitive and reference types. Boolean expressions are explained here in detail, building

from their use in Chapter 6. Some of the basic services of the Character class are intro￾duced.

Chapter 8 describes classes. Classes have been used throughout the text, however,

prior to this chapter, example programs involved a single class as a client of one or more

library classes. Here programs make use of multiple classes. Additionally, class interac￾tion and information hiding principles are explained.

Chapter 9 introduces software development. Classes are used as the decomposition

mechanism using a responsibility-based approach to design. The traditional seven phases

of the software development life cycle are described.

Chapter 10 covers the String class and special processing for text manipulation.

Finally, Chapter 11 covers arrays, including both single- and two-dimensional arrays,

and describes standard array processing techniques.

Each chapter represents approximately one week, or three lecture hours, of material.

Chapters 1, 4, 9, and 11 generally take a bit longer, while some of the other chapters

take slightly less time. By emphasizing or de-emphasizing certain material, the text can

easily accommodate a ten- to thirteen-week course. The sections marked with a star (*)

are optional and can be omitted without loss of context in later chapters. The material in

Appendix A can be used to augment Chapter 1 if this is seen as desirable.

The presentation is sequential and most chapters depend on material presented in

previous chapters. Some of the material from Chapter 1, specifically the sections on

computer software and social issues, may be deferred and introduced wherever conven￾ient. Similarly, the section on syntax in Chapter 2 can be de-emphasized as long as the

syntax descriptions in later chapters are explained as they are introduced.

PREFACE

viii

Features

The text incorporates a number of features to aid the educational process.

Java Syntax The syntax for each new construct is described using the notation of the

Java Language Specification in special boxes called Syntax Boxes. The complete syntax of

Java is found in Appendix B.

Turtle Graphics Early examples and exercises use the Turtle Graphics class library.

With this application, first programs are made interesting and challenging for the stu￾dents.

Style Tips Periodically, tips regarding programming style are included to help the stu￾dent adopt good programming style and become familiar with Java programming con￾ventions. These Style Tips are marked with a special symbol in the margin.

Case Studies Although examples are used throughout the text, most chapters include

an additional extensive example that is presented as a case study. The case studies are

developed following the software development process described in Chapter 1 and

detailed in Chapter 9.

Programming Patterns At appropriate times in the text, I introduce what I call pro￾gramming patterns. These are inspired by design patterns as described in Design

Patterns–Elements of Reusable Object-Oriented Software1, and represent commonly used

patterns of programming language text applicable in a variety of programs. Like design

patterns, these provide larger, abstract components out of which a program can be con￾structed. The programming patterns are marked with a special notation in the margin

and are collected and described in detail in Appendix C.

Students can use programming patterns as templates in writing program code.

Through nesting and merging, patterns can be used to develop fairly sophisticated code.

Programming patterns can also be used by those who have learned another language

prior to Java to help them become accustomed to the Java style of program expression.

Debugging Techniques Many constructs require special consideration in testing and

debugging. When such new constructs, methods or control structures for example, are

introduced, a section on testing and debugging is included to guide the student in tech￾niques that can be used to make this process easier.

Memory Models and Flow Diagrams To help explain the concepts of variables,

assignment, reference versus value semantics, and similar issues, the text uses a simplified

model of memory that diagrams the way information is stored. Similarly, when control

structures are introduced, the flow of control is described by flow diagrams.

PREFACE

ix

1Gamma, E., et al; Design Patterns–Elements of Reusable Object-Oriented Software; Addison￾Wesley, Reading, MA; 1994

Website The source code and Custom Package for this text can be found at:

http://computerscience.jbpub.com/cs_resources.cfm.

Definitions New terms and concepts are written in bold within the text when they

first occur. The more important terms are highlighted in blue and their definitions

appear in a box in the margin. All introduced terms are collected with their definitions in

a Glossary in Appendix D.

Chapter Objectives, Review Questions, and Exercises Each chapter begins with a

list of objectives that are the educational outcomes expected of the chapter. To help the

student judge his/her progress, each chapter ends with a set of review questions, the

answers to which are found in Appendix F, and a set of programming exercises that can

also be used as weekly programming assignments.

Acknowledgements

I would like to take the opportunity of thanking the many people who helped bring this

book to successful completion. First, many thanks to Michael Stranz at Jones & Bartlett

for his confidence in my abilities as an author, and also to Bobbie Lewis and Amy Rose

for all of their work.

Thanks are also owed to the reviewers who reviewed my early manuscript and made

suggestions that much improved the final product: Claude Anderson, Rose-Hulman

Institute of Technology; John Beidler, University of Scranton; Robert Burton, Brigham

Young University; John Connely, California Polytechnic State University; Craig Graci,

State University of New York at Oswego; Ananth Grama, Purdue University; Pamela

Lawhead, The University of Mississippi; Ray Lischner, Oregon State University;

Thomas Mertz, Millersville University; Carolyn Schauble, Colorado State University;

Dale Skrien, Colby College. My co-instructors in COSC 1P02, Dave Bockus and

Sheridan Houghten, provided many insights, examples, review questions, and exercises,

for which I am forever indebted.

Finally, special thanks go to the students of COSC 1P02 over the last two years who

test-drove the manuscript and provided feedback and insights.

Dave Hughes

PREFACE

x

Contents

Preface v

CHAPTER 1 Computing Fundamentals 1

1.1 A Brief History of Computing 3

From Counting to Computing 3

The Modern Era 4

Generations of Computers 6

1.2 Computer Systems 8

Computer Hardware 8

1.3 Data Representation 11

1.4 Computer Software 13

System Software 13

Application Software 14

Software Development Environments 14

1.5 Software Development 15

Software Engineering 15

Programming Languages 17

Program Preparation 20

1.6 Social Issues 21

Summary 25

Review Questions 25

Exercises 26

CHAPTER 2 Java Programs 29

2.1 Java 30

Java: Platform Independent 30

Java: A Modern Language 31

Drawing a Square 31

Java Syntax 33

2.2 Turtle Graphics 36

2.3 Classes 38

Constructors 39

Fields 40

Statements 41

2.4 Looping—The Countable Repetition Pattern 42

Drawing a Hexagon 44

Case Study: Drawing Eight Squares 46

2.5 Execution of Java Programs 49

Summary 50

Review Questions 51

Exercises 53

CHAPTER 3 Computations 55

3.1 Numbers 56

Numeric Types 56

Numeric Literals 57

3.2 Expressions 58

Basic Java Operators 58

Order of Operations 59

Computing Pay—An Example 60

Modes of Arithmetic and Conversion 63

Centering the Square—An Example 64

CONTENTS

xii

3.3 Variables 67

Declaring a Variable 67

Local Variables 68

3.4 Assignment Statement 68

Assignment Compatibility 69

Pay Calculation Revisited 71

Memory Model 72

Case Study: Plotting a Function 74

3.5 Modifying Earlier Examples 77

Pay Calculation—One More Time 77

Scaling the Hexagon 77

Summary 81

Review Questions 82

Exercises 83

CHAPTER 4 Methods 85

4.1 Methods and Abstraction 86

4.2 Simple Methods 87

Eight Squares Revisited 89

Drawing a Scene—An Example 93

4.3 Methods with Parameters 96

Parameter Passing 98

Formal and Actual Parameters 98

Drawing Nested Squares—An Example 99

Drawing a Beach Umbrella—An Example 104

Drawing Rectangles—An Example 106

4.4 Function Methods 109

Function Method Header 109

The return Statement 109

Function Plot Revisited 110

Case Study: Scaling the Plot to Fit the Window 113

4.5 Testing and Debugging with Methods 116

4.6 Methods, Scope, and Visibility 118

Java Scope Rules 118

Scope Rules Illustrated 118

Java Visibility Rules 119

Summary 121

Review Questions 122

Exercises 124

CHAPTER 5 Input and Output 129

5.1 Streams 130

CONTENTS

xiii