NELL DALE JOHN LEWIS
JONES AND BARTLETT COMPUTER SCIENCE
computer science
illuminated
NELL DALE JOHN LEWIS
computer science
illuminated
NELL DALE JOHN LEWIS
computer science
illuminated
University of Texas, Austin Villanova University
Goin’ Live
This step-by-step HTML
Tutorial will guide you from
start to finish as you create
your own website. With each
lesson, you’ll gain experience
and confidence working in the
HTML language.
Online Glossary
We’ve made all the key
terms used in the text easily
accessible to you in this
searchable online glossary.
The Language Library
Here you will find two complete chapters that
supplement the book’s language-neutral approach to
programming concepts. A JAVA language chapter
and C++ language chapter are included and follow
the same pedagogical approach as the textbook.

The Learning Store
Jones and Bartlett Publishers
has a wealth of material
available to supplement the
learning and teaching
experience. Students and
instructors will find
additional resources here or at
http://computerscience.
jbpub.com
Jones and Bartlett Publishers is pleased to provide Computer
Science Illuminated’s
book-specific website. This site offers a
variety of resources designed to address multiple learning styles
and enhance the learning experience.

eLearning
Our eLearning center provides chapter-specific
activities that will actively engage you in the learning
process. Each activity directly correlates to material
presented in the text to help you gain command over
chapter content.
Interactive Review
You can check your
general understanding of
key concepts with this
dynamic chapter review.
Animated Flashcards
Computer science is rich with vocabulary, and these
virtual flashcards will help you quickly master new

terms and definitions.
Did You Know?
Find out more about the fun
facts and stories included as
callouts in the text. Here you’ll
find an extensive collection of
material ranging from historical
information to the latest
technological developments.
Live Wire
Explore the Web through
these links that will send
you to a plethora of
relevant sites that expand
upon the concepts you’ve
discovered in the text.
Cryptic Crossword
Puzzles
For a fun review of
chapter material, challenge
yourself with these
interactive crossword
puzzles.
Ethical Issues
Learn more about the new
social challenges that come
with the development of
computer and Internet
technology through these
discussions and links.

Biographical
Sketches
Be introduced to some of
the many people who have
made substantial
contributions to the
computer science field.
World Headquarters
Jones and Bartlett Publishers
40 Tall Pine Drive
Sudbury, MA 01776
978-443-5000

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
Dale, Nell B.
Computer science illuminated / Nell Dale, John Lewis.
p. cm.
ISBN 0-7637-1760-6
1. Computer science. I. Lewis, John (John Allan), 1963- II. Title.

QA76 . D285 2002
004—dc21 2001050774
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
Senior Marketing Manager: Nathan Schultz
Web Product Manager: Adam Alboyadjian
Senior Development Editor: Dean DeChambeau
Associate Production Editor: Tara McCormick
Editorial Assistant: Theresa DiDonato
Production Assistant: Karen Ferreira
Cover Design: Night & Day Design
Composition: Northeast Compositors
Copyediting: Roberta Lewis
Proofreading: Diane Freed Publishing Services
Illustrations and Technical Art: Smolinski Studios
Printing and Binding: Quebecor World Taunton
Cover Printing: John Pow Company, Inc.
This book was typeset in Quark 4.1 on a Macintosh G4. The font families used were Sabon, Franklin
Gothic, Futura, and Prestige Elite. The first printing was printed on 45# New Era Matte.
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 Sharon and my son Justin—why I do

what I do.
John Lewis
To Al, my husband and best friend, and to Bamsi
Bear, one of man’s best friends, who took care of us
faithfully for 12 years.
Nell Dale
John Lewis, Villanova University
John Lewis is a leading educator and author in the field of computer science.
He has written a market-leading textbook on Java software and program design.
After earning his undergraduate degree, M.S., and Ph.D. in computer science at
Virginia Tech, John joined the faculty of the Department of Computing Sciences at
Villanova University. He has received numerous teaching awards, including the
University Award for Teaching Excellence and the Goff Award for Outstanding
Teaching. His professional interests include object-oriented technologies,
multimedia, and software engineering. In addition to his teaching and writing,
John actively participates in the Special Interest Group on Computer Science
Education (SIGCSE), and finds time to spend with his family or in his workshop.
Nell Dale, University of Texas, Austin
Well respected in the field of Computer Science Education, Nell Dale has served on
the faculty of the University of Texas at Austin for more than 25 years and has
authored over 20 undergraduate Computer Science textbooks. After receiving her
B.S. in Mathematics and Psychology from the University of Houston, Nell entered
the University of Texas at Austin where she earned her M.A. in Mathematics and
her Ph.D. in Computer Science. Nell has made significant contributions to her
discipline through her writing, research, and service. Nell’s contributions were
recognized in 1996 with the ACM SIGCSE Award for Outstanding Contributions
in Computer Science Education. In the summer of 1994, Nell retired from full-time
teaching, giving her more time to write, travel, and play tennis. She currently
resides in Austin, Texas with her husband Al and their dog Maggie.
viii

Laying the Groundwork 3
Chapter 1 The Big Picture . . . . . . . . . . . . . . . . . . . . . . .3
The Information Layer 33
Chapter 2 Binary Values and Number Systems . . . . . .33
Chapter 3 Data Representation . . . . . . . . . . . . . . . . .51
The Hardware Layer 87
Chapter 4 Gates and Circuits . . . . . . . . . . . . . . . . . . .87
Chapter 5 Computing Components . . . . . . . . . . . . . .115
The Programming Layer 141
Chapter 6 Problem Solving and Program Design . . .141
Chapter 7 Low-Level Programming Languages . . . . .187
Chapter 8 High-Level Programming Languages . . . . .225
Chapter 9 Abstract Data Types and Algorithms . . . . .275
The Operating Systems Layer 319
Chapter 10 Operating Systems . . . . . . . . . . . . . . . . .319
Chapter 11 File Systems and Directories . . . . . . . . . .349
The Applications Layer 373
Chapter 12 Information Systems . . . . . . . . . . . . . . .373
Chapter 13 Artificial Intelligence . . . . . . . . . . . . . . . .399
Chapter 14 Simulation and Other Applications . . . . .431
The Communications Layer 455
Chapter 15 Networks . . . . . . . . . . . . . . . . . . . . . . .455
Chapter 16 The World Wide Web . . . . . . . . . . . . . . .479
In Conclusion 501
Chapter 17 Limitations of Computing . . . . . . . . . . . .501
ix
brief contents
Laying the Groundwork
Chapter 1
The Big Picture . . . . . . . . . . . . . . . . . . .3

1.1 Computing Systems 4
Layers of a Computing System 4
Abstraction 7
1.2 The History of Computing 9
A Brief History of Computing Hardware 9
A Brief History of Computing Software 17
Predictions 23
1.3 Computing as a Tool and a Discipline 24
Summary 26
Ethical Issues: Microsoft Anti-Trust Case 27
Key Terms 28
Exercises 28
Thought Questions 31
The Information Layer
Chapter 2
Binary Values and Number Systems . .33
2.1 Number Categories 34
2.2 Natural Numbers 35
Positional Notation 35
Binary, Octal, and Hexadecimal 38
Arithmetic in Other Bases 39
Power of Two Number Systems 40
Converting From Base 10 to Other Bases 42
x Contents
Binary Values and Computers 43
Summary 45
Ethical Issues: The Digital Divide 45
Key Terms 46
Exercises 46
Thought Questions 49

Chapter 3 Data Representation . . . . . . . . . . . . . .51
3.1 Data and Computers 52
Analog and Digital Information 53
Binary Representations 55
3.2 Representing Numeric Data 57
Representing Negative Values 57
Representing Real Numbers 61
3.3 Representing Text 63
The ASCII Character Set 64
The Unicode Character Set 65
Text Compression 66
3.4 Representing Audio Information 70
Audio Formats 72
The MP3 Audio Format 73
3.5 Representing Images and Graphics 73
Representing Color 73
Digitized Images and Graphics 76
Vector Representation of Graphics 77
3.6 Representing Video 78
Video Codecs 78
Summary 79
Ethical Issues: Napster 79
Key Terms 80
Exercises 81
Thought Questions 85
Contents xi
The Hardware Layer
Chapter 4
Gates and Circuits . . . . . . . . . . . . . . .87
4.1 Computers and Electricity 88

4.2 Gates 90
NOT Gate 90
AND Gate 92
OR Gate 92
XOR Gate 93
NAND and NOR Gates 94
Review of Gate Processing 95
Gates with More Inputs 95
4.3 Constructing Gates 96
Transistors 96
4.4 Circuits 99
Combinational Circuits 99
Adders 102
Multiplexers 104
4.5 Circuits as Memory 106
4.6 Integrated Circuits 107
4.7 CPU Chips 108
Summary 108
Ethical Issues: E-mail Privacy 109
Key Terms 110
Exercises 110
Thought Questions 113
Chapter 5 Computing Components . . . . . . . . . .115
5.1 Individual Computer Components 116
5.2 Stored-Program Concept 119
von Neumann Architecture 119
The Fetch-Execute Cycle 124
RAM and ROM 126
Secondary Storage Devices 127
xii Contents

5.3 Non-von Neumann Architectures 131
5.4 Interpreting Ads 133
Summary 134
Ethical Issues: Facial Recognition/Privacy 135
Key Terms 136
Exercises 136
Thought Questions 139
The Programming Layer
Chapter 6
Problem Solving and
Algorithm Design . . . . . . . . . . . . . . . . . . . . . . .141
6.1 Problem Solving 142
How to Solve Problems 143
Computer Problem-Solving 148
Following an Algorithm 149
Developing an Algorithm 151
6.2 Top-Down Design 151
A General Example 153
A Computer Example 155
Summary of Methodology 160
Testing the Algorithm 160
6.3 Object-Oriented Design 162
Object Orientation 163
Relationships between Classes 163
Object-Oriented Design Methodology 164
General Example 169
Computer Example 171
6.4 Important Threads 176
Information Hiding 176
Abstraction 177

Naming Things 178
Programming Languages 179
Testing 179
Contents xiii
Summary 179
Ethical Issues: Plagiarism 180
Key Terms 181
Exercises 182
Thought Questions 185
Chapter 7 Low-Level Programming
Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . .187
7.1 Computer Operations 188
7.2 Levels of Abstraction 189
7.3 Machine Language 189
Pep/7: A Virtual Computer 190
7.4 A Program Example 198
Problem and Algorithm 198
A Program 199
An Alternate Program for the Same Algorithm 203
An Enhanced Version of “Hello” 204
7.5 Assembly Language 207
Pep/7 Assembly Language 207
7.6 Other Important Threads 215
Testing 216
Summary 218
Ethical Issues: Software Piracy, Copyrighting 219
Key Terms 220
Exercises 220
Thought Questions 223
Chapter 8 High-Level Programming

Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . .225
8.1 Translation Process 226
Compilers 226
Interpreters 227
8.2 Programming Language Paradigms 228
8.3 Functionality of Imperative Languages 231
Boolean Expressions 232
Strong Typing 234
Input/Output Structures 239
Control Structures 240
Composite Data Types 257
8.4 Functionality of Object-Oriented Languages 261
Encapsulation 261
xiv Contents
Inheritance 262
Polymorphism 262
Summary 264
Ethical Issues: Hacking 265
Key Terms 266
Exercises 266
Thought Questions 272
Chapter 9 Abstract Data Types
and Algorithms . . . . . . . . . . . . . . . . . . . . . . . . .275
9.1 Abstract Data Types 276
9.2 Implementation 277
Array-Based Implementations 277
Linked Implementation 279
9.3 Lists 282
Basic List Operations 282
Additional List Operations 287

9.4 Sorting 287
Selection Sort 288
Bubble Sort 290
Quicksort 291
9.5 Binary Search 295
9.6 Stacks and Queues 298
Stacks 298
Queues 300
Implementation 300
9.7 Trees 300
Binary Trees 302
Binary Search Trees 303
Other Operations 309
Graphs 310
9.8 Programming Libraries 310
Summary 311
Ethical Issues: Web Content 312
Key Terms 313
Exercises 313
Thought Questions 317
Contents xv
The Operating Systems Layer
Chapter 10
Operating Systems . . . . . . . . . . . . .319
10.1 Roles of an Operating System 320
Memory, Process, and CPU Management 322
Batch Processing 323
Timesharing 324
Other OS Factors 325
10.2 Memory Management 326

Single Contiguous Memory Management 327
Partition Memory Management 329
Paged Memory Management 331
10.3 Process Management 333
The Process States 333
The Process Control Block 334
10.4 CPU Scheduling 335
First-Come, First-Served 336
Shortest Job Next 337
Round Robin 337
Summary 339
Ethical Issues: Privacy Invasion 340
Key Terms 341
Exercises 342
Thought Questions 347
Chapter 11 File Systems and Directories . . . . . .349
11.1 File Systems 350
Text and Binary Files 351
File Types 352
File Operations 353
File Access 354
File Protection 356
11.2 Directories 357
Directory Trees 357
Path Names 359
xvi Contents
11.3 Disk Scheduling 363
First-Come, First-Served Disk Scheduling 364
Shortest-Seek-Time-First Disk Scheduling 365
SCAN Disk Scheduling 365

Summary 366
Ethical Issues: Computer Viruses and Denial of Service 367
Key Terms 368
Exercises 368
Thought Questions 371
The Applications Layer
Chapter 12
Information Systems . . . . . . . . . . .373
12.1 Managing Information 374
12.2 Spreadsheets 375
Spreadsheet Formulas 377
Circular References 382
Spreadsheet Analysis 382
12.3 Database Management Systems 383
The Relational Model 384
Relationships 387
Structured Query Language 388
Database Design 390
Summary 392
Ethical Issues: Encryption 393
Key Terms 394
Exercises 394
Thought Questions 397
Chapter 13 Artificial Intelligence . . . . . . . . . . . .399
13.1 Thinking Machines 400
The Turing Test 401
Contents xvii
Aspects of AI 403
13.2 Knowledge Representation 403
Semantic Networks 404

Search Trees 406
13.3 Expert Systems 409
13.4 Neural Networks 412
Biological Neural Networks 412
Artificial Neural Networks 413
13.5 Natural Language Processing 415
Voice Synthesis 416
Voice Recognition 417
Natural Language Comprehension 418
13.6 Robotics 419
The Sense-Plan-Act Paradigm 420
Subsumption Architecture 421
Physical Components 422
Summary 424
Ethical Issues: Deep Linking 425
Key Terms 426
Exercises 426
Thought Questions 429
Chapter 14 Simulation and Other
Applications . . . . . . . . . . . . . . . . . . . . . . . . . . .431
14.1 What Is Simulation? 432
Complex Systems 432
Models 433
Constructing Models 433
Queuing Systems 435
Meteorological Models 438
Other Models 444
Computing Power Necessary 444
14.2 Graphics and Computer-Aided Design (CAD) 445
14.3 Embedded Systems 447

Summary 449
Ethical Issues: Online Gambling 449
Key Terms 450
Exercises 451
Thought Questions 452
xviii Contents
The Communications Layer
Chapter 15
Networks . . . . . . . . . . . . . . . . . . . .455
15.1 Networking 456
Types of Networks 457
Internet Connections 459
Packet Switching 462
15.2 Open Systems and Protocols 463
Open Systems 463
Network Protocols 464
TCP/IP 465
High-Level Protocols 465
MIME Types 466
Firewalls 467
15.3 Network Addresses 468
Domain Name System 469
Summary 471
Ethical Issues: Cybersquatting 473
Key Terms 474
Exercises 475
Thought Questions 477
Chapter 16 The World Wide Web . . . . . . . . . . .479
16.1 Spinning the Web 480
16.2 HTML 482

Basic HTML Formatting 485
Images and Links 486
16.3 Interactive Web Pages 487
Java Applets 487
Java Server Pages 488
16.4 XML 489
Summary 493
Ethical Issues: Cookies 495
Key Terms 496
Exercises 496
Thought Questions 498
Contents xix
In Conclusion
Chapter 17
Limitations of Computing . . . . . . . .501
17.1 Hardware 502
Limits on Arithmetic 502
Limits on Communications 509
17.2 Software 510
Complexity of Software 511
Current Approaches to Software Quality 512
Notorious Software Errors 516
17.3 Problems 518
Comparing Algorithms 519
Turing Machines 525
Halting Problem 528
Classification of Algorithms 531
Summary 532
Ethical Issues: Licensing Computer Professionals 533
Key Terms 535

Exercises 535
Thought Questions 538
Answers to Selected Exercises 539
Glossary 603
Endnotes 631
Index 639
xx Contents
Preface
W
elcome to Computer Science Illuminated! This book provides a broad
and thorough exploration of computer systems within a computer
science context. Although this is classified as a CS-0 book, we realize
that the term CS-0 means different things to different people.
Independently, both of us have written successful textbooks on various
topics, but this book represents our first opportunity for such a
comprehensive exploration of computing. We're thrilled to join forces to offer
this book.
We take pedagogy seriously—and we know you do, too.
This book is designed as a breadth-first introduction to the field of
computer science, providing a comprehensive and rigorous exploration of a
variety of topics. It provides a general understanding of computers in all their
aspects, and it lays a solid foundation to support further study. Therefore,
this book is appropriate both for computer science majors beginning their
studies and for non-majors seeking a broad but complete overview.
Choice of Topics
We used many sources in putting together the outline of topics for this text.
We looked at course catalogue descriptions and book outlines, and
administered a questionnaire designed to find out what you, our colleagues,
thought should be included in such a course. We answered the following three
questions and asked you to do the same.

• What topics should students master in a CS-0 course if it is the only
computer science course they will take during their college experience?
• What topics should students have mastered before entering your CS-1
course?
Preface xxi
• What additional topics should your CS-1 students be familiar with?
The strong consensus that emerged from the intersections of these sources
formed the working outline for this book. Students who master this material
before taking CS-1 have a strong foundation upon which to continue in computer
science. Although our intention was to write a CS-0 text, our reviewers have
pointed out that the material also forms a strong breadth-first background that
can serve as a companion to a programming-language introduction to computer
science.
Organization
In Chapter 1, we set the stage with the analogy that a computing system is
like an onion that has evolved layer by layer over time. The history of
hardware and software is presented beginning with the computer and
machine language, the heart of the onion. Higher level languages such as
FORTRAN, Lisp, Pascal, C, C++, and Java followed, along with the ever-
increasing understanding of the programming process using such tools as
top-down design and object-oriented design. The operating system with its
resource-management techniques developed to surround and manage these
languages and the programs written in them.
Sophisticated general-purpose and special-purpose software systems that
allowed non-computer people to solve problems were developed to form another
layer. These powerful programs were stimulated by parallel theoretical work in
computer science, which made such programs possible. The final layer is made
up of networks and software—all the tools needed for computers to communicate
with one another. The Internet and the World Wide Web put the finishing touches
on this layer.

Through our teaching experience we have discovered that complex
concepts are easier to understand if handled one layer at a time rather than
in one big bite. Thus, the book is organized into the following sections:
• Information Layer
• Hardware Layer
• Programming Layer
• Operating Systems Layer
• Applications Layer
• Communications Layer
These layers, taken in this order, examine a computer system from the
inside out. Research has shown that students understand concrete examples
more easily than abstract ones even when the students themselves are abstract
thinkers. Thus, we begin with the concrete machine, and add one layer at a
time, each abstracting the details of the previous level, so that other aspects
of computing can be explored. We believe that a thorough understanding
of one layer makes the transition to the next abstraction easier for students.
xxii Preface
Information Layer
Hardware Layer
Programming Layer
Operating Systems Layer
Applications Layer
Communications Layer
Individual chapters within each layer focus on particular aspects of that
layer. The next section provides a synopsis of each chapter.
The design of this book is extremely modular. The layered view of a
computing system provides flexibility to instructors who may choose to
emphasize topics differently or place them in a different order. We revisit the
onion analogy at the opening of each chapter, showing how the current
discussion fits into the big picture.

Synopsis
The first and last chapters of the book form bookends: Chapter 1 describes
what a computing system is and Chapter 17 explores what computing systems
cannot do. The chapters in between look in depth at the layers that make
up a computing system and explain, one step at a time, how a computer does
what it does.
Chapter 1 lays the groundwork for the rest of the book, establishing
terminology and explaining the history of computing. The evolution of the
hardware and software levels that make up the history of computing systems
form much of the underlying structure of the layers explored throughout the
book.
Chapters 2 and 3 examine a layer that is largely conceptual, yet
permeates all other aspects of computer processing. We call this layer the
information layer, and it reflects how information is represented in the
computer. Chapter 2 covers the binary number system and its relationship
to other number systems (such as decimal, the one we humans use on a daily
basis). Chapter 3 investigates how we take the myriad types of information
we manage—numbers, text, images, audio, and video—and represent them
in a binary format.
Chapters 4 and 5 explore the hardware layer. Chapter 4 describes gates
and circuits, which control the flow of electricity in fundamental ways. This
core electronic circuitry gives rise to the discussion in Chapter 5 of specialized
hardware components such as the Central Processing Unit (CPU) and
memory, including how they interact within a von Neumann architecture.
Chapters 6 through 9 cover aspects of the programming layer. Chapter
6 examines the problem-solving process, both human and computer related.
George Polya's human problem-solving strategies guide the discussion.
Examples of both top-down design and object-oriented design are presented.
Chapter 7 covers the concepts of both machine language and assembly
language using Pep/7, a simulated computer. Chapter 8 covers the concepts

of high-level programming languages. The concepts are illustrated in brief
examples from four programming languages: Ada, Visual Basic .NET, C++,
and Java. Chapter 9 emphasizes the role of abstract data types and data
structures in the programming process.
Preface xxiii
Chapters 10 and 11 cover the operating systems layer. Chapter 10
discusses the resource-management responsibilities of the operating system
and presents some of the basic algorithms used to implement those tasks.
Chapter 11 deals with file systems, including what they are and how they are
managed by the operating system.
Chapters 12 through 14 cover the applications layer. This layer is
made up of the general-purpose and specialized application programs that
are available for public use to solve problems. We divide this layer into the
sub-disciplines of computer science upon which these programs are based.
Chapter 12 examines information systems, Chapter 13 examines artificial
intelligence, and Chapter 14 examines simulation, computer-aided design,
and embedded systems.
Chapters 15 and 16 cover the communications layer. Chapter 15
discusses various aspects of computer networks, including how they evolved
and how they manage the transmission of data. Chapter 16 explores the
World Wide Web and some of the technologies that give it the impact it has
today.
Chapter 17 concludes with a discussion of the inherent limitations of
computer hardware, software, and the problems that can and cannot be
solved using a computer. Big-O notation is presented as a way to talk about
the efficiency of algorithms so that the categories of algorithms can be
discussed. The Halting problem is presented to show that some problems are
unsolvable.
Language Issues
Note that the programming layer of this book deals with various aspects of

programming without going into detail on any one language. In fact, we
deliberately present high-level programming constructs in several languages
for students to see a variety of syntax, and to reinforce that the underlying
conceptual ideas are far more important than the particular language used
to implement them.
A more detailed introduction to two high-level programming languages,
Java and C++, are provided on this book’s web site. Any instructor wanting
to expose their students to the details of a language may use these chapters
to supplement the book.
Special Features
We have included three special features in this text in order to emphasize the
history and breadth of computing as well as the moral obligations that come
with new technology. Each chapter includes a Short Biography of someone
who has made a significant contribution to computing. The people honored
in these sections range from those who have contributed to the information
xxiv Preface