Computer science illuminated

NELL DALE JOHN LEWIS

computer science

illuminated

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

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

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

The Big Picture

Chapter 1

This book is a tour through the world of computing. We explore

how computers work—what they do and how they do it, from

bottom to top, inside and out. Like an orchestra, a computer

system is a collection of many different elements, combined to

form a whole that is far more than the sum of its parts. This

chapter provides the big picture, giving an overview of the pieces

that we slowly dissect throughout the book and putting those

pieces into historical perspective.

Most of you have grown up during the age of the personal

computer. Hardware, software, programming, web surfing, and

e-mail are probably familiar terms to you. Some of you can define

these and many more computer-related terms explicitly, whereas

others may have only a vague, intuitive understanding of them.

This chapter gets everyone on relatively equal footing by estab￾lishing common terminology and forming the platform from which

we will dive into our exploration of computing.

3