Preface

Problem Structured Programming In Pascal.There have been many changes in the way the first course in Computer
Science is taught since the first edition of this book was published in 1981.
During the past two years I have been the chairman of the ACM Task
Force that has been studying these changes with an eye towards updating
the description of the recommended first course for Computer Science majors (CS1).l Parallel with this effort, the Educational

Testing Service (ETS)
published a set of guidelines for an Advanced Placement course in Computer Science.f The text has been completely revised and reorganised to
conform to both of these guidelines.
This text can be used in any introductory programming course that emphasizes a careful, disciplined approach to programming in Pascal. Since the Advanced Placement course is a full year course, this text covers more
material than would normally be completed in one semester.

The additional material on searching and sorting algorithms (Chapter 9) and dynamic
data structures (Chapter 10) are optional advanced topics in CS1 and
would normally be deferred until CSZ.
As in the first edition, the primary goal of this text is to illustrate and
teach problem solving through the stepwise development of algorithms. To
facilitate this, procedures are introduced much earlier in this edition.
There are also several large case studies throughout the text that integrate
‘Koffman. E, Miller. P, and Wardle. C. Recommended Curriculum for CS1. 1984. Communications ACM 27.
10 (Oct., 1964). 996-1001.
2 Advanced Placement Program of the College Board. Advanced Placement Course Description: Computer
Science. Educational Testing Service. Princeton. NJ. 1963.

PREFACE

topics and illustrate their application in a substantial programming problem with multiple procedures. Many new examples and programming assignment projects are provided.
Some of the important features of this new edition are:
Early introduction of procedures: Procedures without parameters are introduced in Chapter 2 and are used for self-contained operations that require no global variable access (no side-effects). Procedure parameters
are discussed in Chapter 3. Early coverage of procedures will enable
students to practice the top-down approach from the beginning and to
become more adept at program modularization.
Interactive programming: The emphasis is on modern technology and interactive programming. The majority of examples are written as interactive programs; however, students are shown early how to convert these
programs to run in a batch environment. There are some batch-oriented
examples as well.

New chapter on recursion: There is a new chapter on recursion that provides many examples of recursive procedures and functions. Additional
algorithms for searching and sorting arrays are also provided in this
chapter.

Arrays: Single and multidimensional arrays are covered in one chapter
instead of in two as in the first edition. Similarly, all material on records
is covered in a single chapter.
New expanded case studies: There are a number of new, larger case
studies within the text. The solutions to the case studies are all carefully developed. System structure charts are used to represent the flow of control and data between modules in a program system.
Spiral approach: A spiral approach is used to preview topics such as the
if statement, for statement, and input/output. Features are introduced
as needed rather than overwhelming a student by providing all the details at once.

Pedagogical aids:

• Self-check Exercises are provided at the end of most sections. Solutions to selected exercises are provided at the end of the text.
• Each chapter ends with a Chapter Review section that includes a
summary, a table of new Pascal statements, and review questions.
• Boxed material: Syntax display boxes are used to describe the syntax of each new Pascal statement as it is introduced, while Program
Style boxes discuss the importance of good programming style.
• Error warnings: Each chapter ends with a discussion geared toward
helping students prevent and correct common programming errors.
Several sections discuss debugging techniques.
• Program comments: All programs are carefully commented. Loop in-variants and assertions are shown for some loops. For easy identification, the first and last line of each procedure or program is in blue
type.
New design: The page layout is larger providing more white space and
the overall tone is more user-friendly. The book has been completely redesigned with an eye towards making it easier for students to find figures, examples, programs, and special display boxes. A second colour is
used both to improve the appearance of the text and to clarify illustrations.
Pascal dialects: ANSI standard Pascal is covered in the text. Common
extensions are described in appendixes on ISO standard Pascal, UCSD
Pascal and Turbo Pascal.
Reference appendixes: There are also appendixes covering Pascal language elements, syntax diagrams, character codes, and error messages.
Complete instructor’s manual: An Instructor’s Manual provides a discussion of how to teach the concepts in each chapter. Sample test questions
will be included as well as answers to all exercises, chapter review
questions, and the Programming Projects found at the end of each chapter.
Transparency masters: A set of 131 transparency masters illustrating important concepts is available upon request.

Acknowledgements

Many people participated in the development of this text. The principal reviewers were most essential in finding errors and suggesting improvements. They include: William Eccles, University of South Carolina; Frank
Friedman, Temple University; David Hannay, Union College; Helen
Holzbaur, Temple University; Abraham Kandel, Florida State University;
Raymond Kirsch, LaSalle College; David Moffat, North Carolina State University; Tom Nelson, North Carolina State University; Richard Rinewalt,
University of Texas at Arlington; Paul Ross, Millersville University of
Pennsylvania; Chris Speth, Western Kentucky University; Caroline
Wardle, Boston University; Charles C. Weems, [r., University of Massachusetts at Amherst; and Brad Wilson, Western Kentucky University. I am grateful to all of them for their considerable efforts.
Towards the beginning of this project, several faculty and members of
the Addison-Wesley sales and marketing staffs participated in focus
groups to discuss the first programming course in Pascal. These discussions were helpful in providing direction to the text and clarifying its organization. The faculty are: Linda Ottenstein, Michigan Tech University;
David Neusse, University of Wisconsin at Eau Claire; Richard Rinewalt,
University of Texas at Arlington; Ruth Barton, Michigan State University;
and Howard Edelman, West Chester State University.

Finally, a number of faculty reviewed and commented on preliminary
sections of the text. These faculty include: Gideon Frieder, University of
Michigan; Gary Ford, University of Colorado; Abraham Kandel, Florida
State University; Paul Hanna, Florida State University; M. Main, University of Colorado; Kent Wooldridge, California State University at Chico;
Richard St. Andre, Central Michigan University; C. E. Wolf, Iowa State
University; Angela Wu, American University; Yure Gurevich, University of
PREFACE xi
Michigan; Amir Foroudi, State University of New York at Fredonia; Morris
Rang, 11, Western Illinois University; Peggy R. Ayres, Linn-Benton Community College; Muhammed H. Chaudhary, Millersville University of Pennsylvania; Stanley Thomas, Wake Forest University; R. J. Del Zoppo,
Jamestown Community College; David Rosenlof, Sacramento City College;

George Beekman, Oregon State University; George Witter, Western Washington State University; J. M. Adams, New Mexico State University; John Lushbough, University of South Dakota; Dave Valentine, State University
of New York at Potsdam; Dennis Martin, State University of New York at
Brockport; Chris J. Dovolis, University of Minnesota; Barbara SmithThomas, University of North Carolina at Greensboro; Barent Johnson, University of Wisconsin at Oshkosh; Carl Wehner, University of Northern
Iowa; Aboalfazl Salimi, Embry-Riddle University; Larry Wilson, Old Dominion University; Cary Laxer, Rose-Hulman Institute of Technology; J.Mailen Kootsey, Duke University; Jerry Waxman, City University of New
York at Queens; Bruce J. Klein, Grand Valley State College; Eris Pas, Duke
University; Gove Effinger, Bates College; Krishna Moorthy, Framingham
State College; Brian Johnson, University of New Hampshire; and John
Coda, Georgia Institute of Technology.

There were also many people involved with the actual production of the
text. From Addison-Wesley, James DeWolf was the sponsoring editor and
recruited reviewers, provided input and suggestions during the writing
stage, and coordinated with the production staff. Bill Gruener also was the
publisher with overall responsibility for the text. Karen Guardino was the
production manager and saw to it that the book was able to meet a very
tight production schedule. Maureen Langer refined the design of the text.
In Philadelphia, Fran Palmer Fulton served as the Production Editor and
coordinated and supervised the typesetting of the manuscript. I am grateful to all of them for their involvement and extra efforts to get this book
published on schedule.

Introduction to

Computers and Programming

1.1 Electronic Computers Then and Now
1.2 Components of a Computer
1.3 Problem Solving and Programming
1.4 Programming Languages
1.5 Processing a High-level Language Program
1.6 Introduction to Pascal
1.7 General Form of a Pascal Program
1.8 Using the Computer
1.9 Formatting Program Output
1.10 Introduction to Data Types
1.11 Common Programming Errors
1.12 Chapter Review

This chapter introduces computers and computer programming. It begins
with a brief history of computers and describes the major components of a
computer including memory, central processor, input devices, and output
devices. The chapter discusses how information is represented in a computer and how it is manipulated.
The major categories of programming languages are introduced. Simple
computer operations are described along with some short programs that
demonstrate these operations. There is a brief introduction to the Pascal
programming language focusing on statements for reading and displaying
information and for performing simple computations.
Also described are the steps involved in creating a Pascal program and
the roles performed by various programs that are part of a computer system. These programs include the operating system, compiler, editor, and
loader.

Electronic Computers Then and Now

It is difficult to live in today’s society without having had some contact
with computers. Computers are used to provide instructional material in
some schools, print transcripts, send out bills, reserve airline and concert
tickets, play games, and even help authors write books.
However, it wasn’t always this way. Just a short time ago, computers
were fairly mysterious devices that only a small percentage of our population knew much about. Computer “know-how” turned around when advances in solid-state electronics led to drastic cuts in the size and costs of
electronic computers. Today, a personal computer (see color insert, Fig.
1.1) which costs less than $3000 and sits on a desk, has as much computational power as one that 10 years ago would have cost more than $100,000
and would fill a 9 by 12 ft room. This price reduction is even more remarkable when we consider the effects of inflation over the last decade.
If we take the literal definition for computer as a device for counting or
computing, then the abacus might be considered the first computer. However, the first electronic digital computer was designed in the late 1930s by
Dr. John Atanasoff at Iowa State University. Atanasoff designed his computer to perform mathematical computations for graduate students.
The first large-scale, general-purpose electronic digital computer, called
the ENIAC, was built in 1946 at the University of Pennsylvania. Its design
was funded by the U. S. Army, and it was used for computing ballistics tables, for weather prediction, and for atomic energy calculations. The
ENIAC weighed 30 tons and occupied a 30 by 50 ft space (see color insert,

Fig. 1.2).

Although we are often led to believe otherwise, computers cannot think!
They are basically devices for performing computations at incredible
speeds (more than one million operations per second) and with great accuracy. However, in order to accomplish anything useful, a computer must
be programmed or given a sequence of explicit instructions (the program)
to carry out.
To program the ENIAC it was necessary to connect hundreds of wires
and arrange thousands of switches in a certain way. In 1946, Dr. John von
Neumann of Princeton University proposed the concept of a stored program computer. The instructions of a program would be stored in computer memory rather than be set by wires and switches. Since the contents of
computer memory can be easily changed, it would not be nearly as difficult to reprogram this computer to perform different tasks as it was to reprogram the ENIAC. Von Neumann’s design is the basis of the digital
computer as we know it today.

 

2 INTRODUCTION TO COMPUTERS AND PROGRAMMING

II Components of a Computer

Despite large variation in cost, size, and capabilities, modern computers
are remarkably similar in a number of ways. Basically, a computer consists of the five components shown in Fig. 1.3 (see color insert). The arrows connecting the components show the direction of information flow.
All information that is to be processed by a computer must first be entered into the computer memory via an input device. The information in
memory is manipulated by the central processor and the results of this
manipulation are stored in memory. Information in memory can be
displayed through an output device. A secondary storage device is often
used for storing large quantities of information in a semi-permanent form.
These components and their interaction are described in more detail in the
following sections.
Computer Memory
Computer memory is used for information storage. All types of information-numbers, names, lists, and even pictures-may be represented and
stored in a computer memory.
The memory of a computer may be pictured as an ordered sequence of
storage locations called memory cells. In order to be able to store and retrieve (access) information, there must be some way to identify the individual memory cells. To accomplish this, each memory cell has associated
with it a unique address that indicates its relative position in memory. Figure 1.4 shows a computer memory consisting of 1000 memory cells with
addresses a through 999. Some large-scale computers have memories consisting of millions of individual cells.
The information stored in a memory cell is called the contents of a
memory cell. Every memory cell always contains some information although we may have no idea what that information is. Whenever new information is placed in a memory cell, any information already there is
destroyed and cannot be retrieved. In Fig. 1.4, the contents of memory cell
3 is the number -26, and the contents of memory cell 4 is the letter H.
Central Processor Unit
The central processor unit (CPU) performs the actual processing or manipulation of information stored in memory. The CPU can retrieve information from memory. (This information may be either data or instructions for
manipulating data.] It can also store the results of these manipulations
back in memory for later use.
The control unit within the CPU coordinates all activities of the computer. It determines which operations should be carried out and in what order; the control unit then transmits coordinating control signals to the
computer components.

Problem Solving and Programming

We mentioned earlier that a computer cannot think; therefore, in order to
get it to do any useful work, a computer must be provided with a program
that is a list of instructions. Programming a computer is a lot more involved than simply writing a list of instructions. Problem solving is an important component of programming. Before we can write the program to
solve a problem, we must consider carefully all aspects of the problem
and then organise its solution.
Like most programming students, you will probably spend a great deal
of time initially in the computer laboratory entering your programs. You
will spend more time later removing the errors or bugs that inevitably will
be present in your programs.
It is tempting to rush to the computer laboratory and start entering your
program as soon as you have some idea of how to write it. You should resist this temptation and instead think carefully about the problem and its solution before writing any program statements. When you have a solution
in mind, you should plan it out on paper and modify it if necessary before
writing the program.

Once the program is written on paper, you should desk check your solution by “executing” it much as the computer would. You should carefully
determine the result of each program statement using sample data that are
easy to manipulate (e.g, small whole numbers). You should compare these
results with what would be expected and make any necessary corrections
to the program when the results are incorrect. Only then should you go to
the computer laboratory and start to enter the program. Experience has
shown that a few extra minutes spent evaluating the proposed solution in
this way often saves hours of frustration later. The process you should follow is shown in Fig. 1.10.
In this text, we will stress a methodology for problem solving that we
have found useful in helping students to learn to program. We will teach a
technique called structured programming that should enable you to write
programs that are relatively easy to read and understand and that contain
fewer initial errors.
Most students have very strong positive or negative feelings about programming; very few students are ambivalent. Some of the reasons thatprogramming can be less than enjoyable are the following:

1. You are learning a new language with its own syntax or rules of grammar.
2. You must carefully plan out what actions you would like performed
   and their sequence.
3. You must be explicit and accurate in describing what you wish done.
4. You must implement your solution in an existing programming language. What seems simple to write in English may require considerable effort to specify in a programming language.
5. You must carefully enter all program instructions and all data since

Contents

Introduction to Computers and Programming 1
1.1 Electronic Computers Then and Now 2
1.2 Components of a Computer 3
1.3 Problem Solving and Programming 6
1.4 Programming Languages 7
1.5 Processing a High-level Language Program 9
1.6 Introduction to Pascal 11
1.7 General Form of a Pascal Program 22
1.8 Using the Computer 26
1.9 Formatting Program Output 29
1.10 Introduction to Data Types 34
1.11 Common Programming Errors 36
1.12 Chapter Review 39
Problem Solving 45
2.1 Representing and Refining Algorithms 46
2.2 Using Procedures for Sub-problems 52
2.3 Decision Steps in Algorithms 59
2.4 Tracing a Program or Algorithm 67
2.5 Problem Solving Strategies 69

xlv CONTENTS
2.6 Repetition in Programs 72
2.7 Generalising a Solution 79
2.8 Repeating a Program Body 83
2.9 Debugging and Testing Programs 87
2.10 Common Programming Errors 88
2.11 Chapter Review 89
Control Statements 95
3.1 Syntax Diagrams 96
3.2 The if Statement Revisited 97
3.3 The while Statement 104
3.4 Procedure Parameters 111
3.5 Adding Data Flow Information to Structure Charts 128
3.6 Nested Procedures and Scope of Identifiers 132
3.7 Case Studies 136
3.8 Debugging a Program System 150
3.9 Common Programming Errors 151
3.10 Chapter Review 152
Simple Data Types 159
4.1 Constant Declarations 160
4.2 Numeric Data Types-REAL and INTEGER 161
4.3 Functions in Arithmetic Expressions 169
4.4 BOOLEAN Variables, Expressions, and Operators 175
4.5 Character Variables and Functions 180
4.6 Introduction to Programmer-defined Data Types 188
4.7 Input/Output Revisited 193
4.8 Case Study 201
4.9 Common Programming Errors 206
4.10 Chapter Review 207
More Control Statements 217
5.1 The case Statement 218
5.2 Set Values in Decisions 221
5.3 The General for Statement 223
II
5.4 The repeat Statement 225
5.5 Nested Loops 229
5.6 User-defined Functions 234
5.7 Case Studies 240
5.8 Common Programming Errors 251
5.9 Chapter Review 252
Arrays 263
6.1 Declaring and Referencing Arrays 264
6.2 Arrays with Integer Subscripts 266
6.3 Case Study 270
6.4 Manipulating Entire Arrays 276
6.5 Reading Part of an Array 282
6.6 General Arrays 283
6.7 Character Strings 288
6.8 Multidimensional Arrays 295
6.9 Case Study 302
6.10 Common Programming Errors 313
6.11 Chapter Review 313
Records 325
7.1 Declaring a Record 326
7.2 Manipulating Individual Fields of a Record 328
7.3 Manipulating an Entire Record 331
7.4 Arrays of Records 334
7.5 Case Study 335
7.6 Searching an Array 342
7.7 Sorting an Array 344
7.8 General Data Structures 348
7.9 Record Variants 352
7.10 Manipulating Strings Stored in Records 357
7.11 Common Programming Errors 363
7.12 Chapter Review 364
CONTENTS xv
II Sets and Files 371
8.1 Set Data Type and Set Operators 372
8.2 RESET, REWRITE, and the File Position Pointer
8.3 TEXT Files 381
8.4 Case Studies 385
8.5 User-defined File Types 396
8.6 Case Study-File Merge 401
8.7 Case Study-Data Base Inquiry 405
8.8 File Buffer Variable 411
8.9 Common Programming Errors 416
8.10 Chapter Review 417
379
II Recursion, Searching, and Sorting
9.1 The Nature of Recursion 426
9.2 Recursive Procedures 432
9.3 Recursive Functions 439
9.4 Binary Search of an Array 449
9.5 Searching by Hashing 453
9.6 Additional Sorting Algorithms 457
9.7 Case Study-The Quicksort Algorithm
9.8 Common Programming Errors 467
9.9 Chapter Review 468

xvi CONTENTS
Pointer Variables and Dynamic Data Structures
10.1 The NEW Statement and Pointer Variables 476
10.2 Understanding Dynamic Allocation 480
10.3 Introduction to Linked Lists 481
10.4 Manipulating Linked Lists Using Pointer Variables 483
10.5 Case Study-Maintaining a Linked List 487
10.6 Stacks and Queues 500
10.7 Multiple-linked Lists and Trees 506
10.8 Case Study-Maintaining a Binary Search Tree 511
10.9 Common Programming Errors 518
10.10 Chapter Review 519

Introduction to Computers and Programming

1.1 Electronic Computers Then and Now
1.2 Components of a Computer
1.3 Problem Solving and Programming
1.4 Programming Languages
1.5 Processing a High-level Language Program
1.6 Introduction to Pascal
1.7 General Form of a Pascal Program
1.8 Using the Computer
1.9 Formatting Program Output
1.10 Introduction to Data Types
1.11 Common Programming Errors
1.12 Chapter Review
This chapter introduces computers and computer programming. It begins
with a brief history of computers and describes the major components of a
computer including memory, central processor, input devices, and output
devices. The chapter discusses how information is represented in a computer and how it is manipulated.
The major categories of programming languages are introduced. Simple
computer operations are described along with some short programs that
demonstrate these operations. There is a brief introduction to the Pascal
programming language focusing on statements for reading and displaying
information and for performing simple computations.

Also described are the steps involved in creating a Pascal program and
the roles performed by various programs that are part of a computer system. These programs include the operating system, compiler, editor, and
loader.

Computer Memory

Computer memory is used for information storage. All types of information-numbers, names, lists, and even pictures-may be represented and
stored in a computer memory.
The memory of a computer may be pictured as an ordered sequence of
storage locations called memory cells. In order to be able to store and retrieve (access) information, there must be some way to identify the individual memory cells. To accomplish this, each memory cell has associated
with it a unique address that indicates its relative position in memory. Figure 1.4 shows a computer memory consisting of 1000 memory cells with
addresses a through 999. Some large-scale computers have memories consisting of millions of individual cells.
The information stored in a memory cell is called the contents of a
memory cell. Every memory cell always contains some information although we may have no idea what that information is. Whenever new information is placed in a memory cell, any information already there is
destroyed and cannot be retrieved. In Fig. 1.4, the contents of memory cell
3 is the number -26, and the contents of memory cell 4 is the letter H.

Central Processor Unit

The central processor unit (CPU) performs the actual processing or manipulation of information stored in memory. The CPU can retrieve information from memory. (This information may be either data or instructions for
manipulating data.] It can also store the results of these manipulations
back in memory for later use.
The control unit within the CPU coordinates all activities of the computer. It determines which operations should be carried out and in what order; the control unit then transmits coordinating control signals to the
computer components.