Computer Science Illuminated, 7th Edition PDF

COMPUTER SCIENCE ILLUMINATED S EVEN TH ED I TI ON N ELL DA LE THE U NIVERSI T Y OF T EXAS AT AUST I N JO HN LEWIS VI RGI NI A T ECH World Headquarters Jones & Bartlett Learning 5 Wall Street Burlington, MA 01803 978-443-5000 [email protected] www.jbl...

COMPUTER SCIENCE ILLUMINATED S EVEN TH ED I TI ON N ELL DA LE THE U NIVERSI T Y OF T EXAS AT AUST I N JO HN LEWIS VI RGI NI A T ECH World Headquarters Jones & Bartlett Learning 5 Wall Street Burlington, MA 01803 978-443-5000 [email protected] www.jblearning.com Jones & Bartlett Learning books and products are available through most bookstores and online booksellers. To contact Jones & Bartlett Learning directly, call 800-832-0034, fax 978-443-8000, or visit our website, www.jblearning.com. Substantial discounts on bulk quantities of Jones & Bartlett Learning publications are available to corporations, professional associations, and other qualified organizations. For details and specific discount information, contact the special sales department at Jones & Bartlett Learning via the above contact information or send an email to [email protected]. Copyright © 2020 by Jones & Bartlett Learning, LLC, an Ascend Learning Company All rights reserved. No part of the material protected by this copyright may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner. The content, statements, views, and opinions herein are the sole expression of the respective authors and not that of Jones & Bartlett Learning, LLC. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not constitute or imply its endorsement or recommendation by Jones & Bartlett Learning, LLC, and such reference shall not be used for advertising or product endorsement purposes. All trademarks displayed are the trademarks of the parties noted herein. Computer Science Illuminated, Seventh Edition is an independent publication and has not been authorized, sponsored, or otherwise approved by the owners of the trademarks or service marks referenced in this product. There may be images in this book that feature models; these models do not necessarily endorse, represent, or participate in the activities represented in the images. Any screenshots in this product are for educational and instructive purposes only. Any individuals and scenarios featured in the case studies throughout this product may be real or fictitious, but are used for instructional purposes only. 15601-0 Production Credits Cover Design: Kristin E. Parker VP, Product Management: Amanda Martin Text Design: Kristin E. Parker Director of Product Management: Laura Pagluica Director, Content Services and Licensing: Joanna Gallant Product Assistant: Loren-Marie Durr Rights & Media Manager: Shannon Sheehan Director of Production: Jenny L. Corriveau Rights & Media Specialist: Thais Miller Project Specialist, Navigate: Rachel DiMaggio Cover Image (Title Page, Part Opener, Chapter Opener): Project Specialist: Alex Schab © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Digital Project Specialist: Angela Dooley Images/Getty Images Marketing Manager: Michael Sullivan Printing and Binding: LSC Communications Product Fulfillment Manager: Wendy Kilborn Cover Printing: LSC Communications Composition: codeMantra U.S. LLC Library of Congress Cataloging-in-Publication Data Names: Dale, Nell (Nell B.) author. | Lewis, John, 1963- author. Title: Computer science illuminated / Nell Dale and John Lewis. Description: Seventh edition. | Burlington, Massachusetts: Jones & Bartlett Learning, | Includes bibliographical references and index. Identifiers: LCCN 2018023082 | ISBN 9781284155617 (pbk.) Subjects: LCSH: Computer science. Classification: LCC QA76.D285 2019 | DDC 004—dc23 LC record available at https://lccn.loc.gov/2018023082 6048 Printed in the United States of America 22 21 20 19 18   10 9 8 7 6 5 4 3 2 1 © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images To all the students who will use this book: It is written for you. —Nell Dale To my wife, Sharon, and our children, Justin, Kayla, Nathan, and Samantha. —John Lewis iii © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Nell Dale, The University of Texas at 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 40 undergraduate computer science textbooks. After receiving her BS in Mathematics and Psychology from the University of Houston, Nell entered The University of Texas at Austin, where she earned her MA in Mathematics and her PhD 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 and in 2001 with the ACM Karl V. Karlstrom Outstanding Educator Award. She was elected an ACM Fellow in 2010. In 2013, she received the IEEE Taylor L. Booth Education Award. Nell has retired from full-time teaching, giving her more time to write, travel, and play tennis and bridge. She lives in Austin, Texas. John Lewis, Virginia Tech 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 PhD in Computer Science, John spent 14 years at Villanova University in Pennsylvania. He now teaches com- puting at Virginia Tech, his alma mater, and works on textbook projects out of his home. 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 teach- ing and writing, John actively participates in the ACM Special Interest Group on Computer Science Education (SIGCSE) and finds time to spend with his family and in his workshop. iv BRIEF CONTENTS © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 1 Laying the Groundwork...................... 2 Chapter 1 The Big Picture   3 2 The Information Layer...................... 34 Chapter 2 Binary Values and Number Systems   35 Chapter 3 Data Representation  55 3 The Hardware Layer........................ 92 Chapter 4 Gates and Circuits  93 Chapter 5 Computing Components  121 4 The Programming Layer.................... 150 Chapter 6 Low-Level Programming Languages and Pseudocode  151 Chapter 7 Problem Solving and Algorithms  191 Chapter 8 Abstract Data Types and Subprograms  241 Chapter 9 Object-Oriented Design and High-Level Programming Languages  281 5 The Operating Systems Layer................ 328 Chapter 10 Operating Systems  329 Chapter 11 File Systems and Directories  361 6 The Applications Layer..................... 386 Chapter 12 Information Systems  387 Chapter 13 Artificial Intelligence  419 Chapter 14 S imulation, Graphics, Gaming, and Other Applications  453 7 The Communications Layer.................. 494 Chapter 15 Networks  495 Chapter 16 The World Wide Web  525 Chapter 17 Computer Security  557 8 In Conclusion............................ 586 Chapter 18 Limitations of Computing  587 v CONTENTS © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 1 Laying the Groundwork............. 2 Chapter 1 The Big Picture   3 1.1 Computing Systems  4 Layers of a Computing System   4 Abstraction  6 1.2 The History of Computing   9 A Brief History of Computing Hardware   9 A Brief History of Computing Software   19 Predictions  25 1.3 Computing as a Tool and a Discipline   26 The Big Ideas of Computing    27 Summary  28 Ethical Issues: Digital Divide   30 Key Terms  31 Exercises  31 Thought Questions  33 2 The Information Layer............. 34 Chapter 2 Binary Values and Number Systems   35 2.1 Numbers and Computing   36 2.2 Positional Notation  36 Binary, Octal, and Hexadecimal   38 Arithmetic in Other Bases   41 Power-of-2 Number Systems   42 Converting from Base 10 to Other Bases   44 Binary Values and Computers   45 Summary  48 Ethical Issues: The FISA Court   49 Key Terms  49 Exercises  50 Thought Questions  53 Chapter 3 Data Representation  55 3.1 Data and Computers   56 Analog and Digital Data   57 vi  vii Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Binary Representations  59 3.2 Representing Numeric Data   61 Representing Negative Values   61 Representing Real Numbers   65 3.3 Representing Text  68 The ASCII Character Set   69 The Unicode Character Set   70 Text Compression  71 3.4 Representing Audio Data  77 Audio Formats  79 The MP3 Audio Format   79 3.5 Representing Images and Graphics  80 Representing Color  80 Digitized Images and Graphics   82 Vector Representation of Graphics   83 3.6 Representing Video  84 Video Codecs  84 Summary  85 Ethical Issues: The Fallout from Snowden’s Revelations   86 Key Terms  86 Exercises  87 Thought Questions  91 3 The Hardware Layer............... 92 Chapter 4 Gates and Circuits  93 4.1 Computers and Electricity  94 4.2 Gates  96 NOT Gate  96 AND Gate  97 OR Gate  98 XOR Gate  98 NAND and NOR Gates   99 Review of Gate Processing   100 Gates with More Inputs   101 viii Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 4.3 Constructing Gates  101 Transistors  102 4.4 Circuits  104 Combinational Circuits  104 Adders  108 Multiplexers  110 4.5 Circuits as Memory  111 4.6 Integrated Circuits  112 4.7 CPU Chips  113 Summary  113 Ethical Issues: Codes of Ethics  114 Key Terms  116 Exercises  116 Thought Questions  119 Chapter 5 Computing Components  121 5.1 Individual Computer Components  122 5.2 The Stored-Program Concept  126 von Neumann Architecture   128 The Fetch–Execute Cycle   132 RAM and ROM   134 Secondary Storage Devices   135 Touch Screens  139 5.3 Embedded Systems  141 5.4 Parallel Architectures  142 Parallel Computing  142 Classes of Parallel Hardware   144 Summary  145 Ethical Issues: Is Privacy a Thing of the Past?   146 Key Terms  146 Exercises  147 Thought Questions  149  ix Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 4 The Programming Layer........... 150 Chapter 6 Low-Level Programming Languages and Pseudocode  151 6.1 Computer Operations  152 6.2 Machine Language  152 Pep/9: A Virtual Computer   153 Input and Output in Pep/9    159 6.3 A Program Example  159 Pep/9 Simulator  160 Another Machine-Language Example    162 6.4 Assembly Language  163 Pep/9 Assembly Language   164 Numeric Data, Branches, and Labels   166 Loops in Assembly Language    170 6.5 Expressing Algorithms  171 Pseudocode Functionality  171 Following a Pseudocode Algorithm   175 Writing a Pseudocode Algorithm   177 Translating a Pseudocode Algorithm   180 6.6 Testing  182 Summary  183 Ethical Issues: Software Piracy  185 Key Terms  186 Exercises  186 Thought Questions  189 Chapter 7 Problem Solving and Algorithms  191 7.1 How to Solve Problems  192 Ask Questions  193 Look for Familiar Things   193 Divide and Conquer   194 Algorithms  194 Computer Problem-Solving Process   196 Summary of Methodology   197 Testing the Algorithm   198 x Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 7.2 Algorithms with Simple Variables  199 An Algorithm with Selection   199 Algorithms with Repetition   200 7.3 Composite Variables  206 Arrays  206 Records  207 7.4 Searching Algorithms  208 Sequential Search  208 Sequential Search in a Sorted Array   209 Binary Search  212 7.5 Sorting  214 Selection Sort  215 Bubble Sort  218 Insertion Sort  220 7.6 Recursive Algorithms  221 Subprogram Statements  221 Recursive Factorial  223 Recursive Binary Search   224 Quicksort  224 7.7 Important Threads  228 Information Hiding  228 Abstraction  229 Naming Things  230 Testing  231 Summary  231 Ethical Issues: Open-Source Software  232 Key Terms  234 Exercises  234 Thought Questions  239 Chapter 8 Abstract Data Types and Subprograms  241 8.1 What Is an Abstract Data Type?  242 8.2 Stacks  242 8.3 Queues  243 8.4 Lists  244  xi Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 8.5 Trees  247 Binary Trees  247 Binary Search Trees   249 Other Operations  255 8.6 Graphs  256 Creating a Graph   258 Graph Algorithms  259 8.7 Subprograms  265 Parameter Passing  266 Value and Reference Parameters   268 Summary  271 Ethical Issues: Workplace Monitoring  273 Key Terms  274 Exercises  274 Thought Questions  279 Chapter 9 Object-Oriented Design and High-Level Programming Languages  281 9.1 Object-Oriented Methodology  282 Object Orientation  282 Design Methodology  283 Example  286 9.2 Translation Process  291 Compilers  292 Interpreters  292 9.3 Programming Language Paradigms  295 Imperative Paradigm  295 Declarative Paradigm  296 9.4 Functionality in High-Level Languages  298 Boolean Expressions  299 Data Typing  301 Input/Output Structures  305 Control Structures  307 9.5 Functionality of Object-Oriented Languages  313 Encapsulation  313 Classes  314 xii Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Inheritance  316 Polymorphism  317 9.6 Comparison of Procedural and Object-Oriented Designs  318 Summary  319 Ethical Issues: Hoaxes and Scams  321 Key Terms  322 Exercises  323 Thought Questions  327 5 The Operating Systems Layer....... 328 Chapter 10 Operating Systems  329 10.1 Roles of an Operating System   330 Memory, Process, and CPU Management   332 Batch Processing  333 Timesharing  334 Other OS Factors   335 10.2 Memory Management  336 Single Contiguous Memory Management   338 Partition Memory Management   339 Paged Memory Management   341 10.3 Process Management  344 The Process States   344 The Process Control Block   345 10.4 CPU Scheduling  346 First Come, First Served   347 Shortest Job Next   348 Round Robin  348 Summary  350 Ethical Issues: Medical Privacy: HIPAA  352 Key Terms  353 Exercises  354 Thought Questions  359 Chapter 11 File Systems and Directories  361 11.1 File Systems  362 Text and Binary Files   362 File Types  363  xiii Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images File Operations  365 File Access  366 File Protection  367 11.2 Directories  368 Directory Trees  369 Path Names  371 11.3 Disk Scheduling  373 First-Come, First-Served Disk Scheduling   375 Shortest-Seek-Time-First Disk Scheduling   375 SCAN Disk Scheduling   376 Summary  378 Ethical Issues: Privacy: Opt-In or Opt-Out?  380 Key Terms  381 Exercises  381 Thought Questions  385 6 The Applications Layer............ 386 Chapter 12 Information Systems  387 12.1 Managing Information  388 12.2 Spreadsheets  389 Spreadsheet Formulas  391 Circular References  396 Spreadsheet Analysis  397 12.3 Database Management Systems  399 The Relational Model   399 Relationships  403 Structured Query Language   404 Database Design  405 12.4 E-Commerce  407 12.5 Big Data  408 Summary  409 Ethical Issues: Politics and the Internet  411 Key Terms  413 Exercises  413 Thought Questions  417 xiv Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Chapter 13 Artificial Intelligence  419 13.1 Thinking Machines  420 The Turing Test   421 Aspects of AI   423 13.2 Knowledge Representation  423 Semantic Networks  425 Search Trees  427 13.3 Expert Systems  430 13.4 Neural Networks  432 Biological Neural Networks   432 Artificial Neural Networks   433 13.5 Natural-Language Processing  435 Voice Synthesis  437 Voice Recognition  438 Natural-Language Comprehension  439 13.6 Robotics  440 The Sense–Plan–Act Paradigm   441 Subsumption Architecture  441 Physical Components  443 Summary  445 Ethical Issues: Initial Public Offerings  447 Key Terms  448 Exercises  448 Thought Questions  451 Chapter 14 Simulation, Graphics, Gaming, and Other Applications  453 14.1 What Is Simulation?   454 Complex Systems  454 Models  455 Constructing Models  455 14.2 Specific Models  457 Queuing Systems  457 Meteorological Models  461 Computational Biology  466  xv Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Other Models  467 Computing Power Necessary   467 14.3 Computer Graphics  468 How Light Works   470 Object Shape Matters   472 Simulating Light  472 Modeling Complex Objects   474 Getting Things to Move   480 14.4 Gaming  482 History of Gaming   483 Creating the Virtual World   484 Game Design and Development   485 Game Programming  486 Summary  487 Ethical Issues: Gaming as an Addiction  489 Key Terms  490 Exercises  490 Thought Questions  493 7 The Communications Layer......... 494 Chapter 15 Networks  495 15.1 Networking  496 Types of Networks   497 Internet Connections  500 Packet Switching  502 15.2 Open Systems and Protocols   504 Open Systems  504 Network Protocols  505 TCP/IP  506 High-Level Protocols  507 MIME Types  508 Firewalls  509 15.3 Network Addresses  510 Domain Name System   511 Who Controls the Internet?   514 xvi Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 15.4 Cloud Computing  515 15.5 Blockchain  516 Summary  517 Ethical Issues: The Effects of Social Networking  519 Key Terms  520 Exercises  521 Thought Questions  523 Chapter 16 The World Wide Web  525 16.1 Spinning the Web   526 Search Engines  527 Instant Messaging  528 Weblogs  529 Cookies  530 Web Analytics  530 16.2 HTML and CSS   531 Basic HTML Elements   535 Tag Attributes  536 More About CSS   537 More HTML5 Elements   540 16.3 Interactive Web Pages   541 Java Applets  541 Java Server Pages   542 16.4 XML  543 16.5 Social Network Evolution   547 Summary  548 Ethical Issues: Gambling and the Internet  551 Key Terms  552 Exercises  552 Thought Questions  555 Chapter 17 Computer Security  557 17.1 Security at All Levels   558 Information Security  558  xvii Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images 17.2 Preventing Unauthorized Access   560 Passwords  561 CAPTCHA  563 Fingerprint Analysis  564 17.3 Malicious Code  565 Antivirus Software  566 Security Attacks  567 17.4 Cryptography  569 17.5 Protecting Your Information Online   572 Corporate Responsibility  574 Security and Portable Devices   574 WikiLeaks  575 Summary  578 Ethical Issues: Blogging and Journalism  580 Key Terms  581 Exercises  582 Thought Questions  585 8 In Conclusion................... 586 Chapter 18 Limitations of Computing  587 18.1 Hardware  588 Limits on Arithmetic   588 Limits on Components   594 Limits on Communications   595 18.2 Software  596 Complexity of Software   596 Current Approaches to Software Quality   597 Notorious Software Errors   602 18.3 Problems  604 Comparing Algorithms  605 Turing Machines  612 Halting Problem  615 Classification of Algorithms   617 xviii Contents © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Summary  619 Ethical Issues: Therac-25: Anatomy of a Disaster  620 Key Terms  621 Exercises  621 Thought Questions  624 Glossary  625 Endnotes  651 Index  661 PREFACE © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Choice of Topics In putting together the outline of topics for this CS0 text, we used many sources. We looked at course catalogue descriptions and book outlines, and we administered a questionnaire designed to find out what you, our colleagues, thought should be included in such a course. We asked you and ourselves to do the following: Please list four topics that you feel students should master in a CS0 course if this is the only computer science course they will take during their college experience. Please list four topics that you would like students entering your CS1 course to have mastered. Please list four additional topics that you would like your CS1 students to be familiar with. The strong consensus that emerged from the intersections of these sources formed the working outline for this book. It serves as a core CS0 text, provid- ing a breadth-first introduction to computing. It is appropriate for use for a course embracing the AP Computer Science Principles curriculum, and alter- natively as a companion or lead-in to a programming intensive course. Rationale for Organization This book begins with the history of hardware and software, showing how a computer system is like an onion. The processor and its machine language form the heart of the onion, and layers of software and more sophisticated hardware have been added around this heart, layer by layer. At the next layer, higher-level languages such as FORTRAN, Lisp, Pascal, C, C++, and Java were introduced parallel to the ever-increasing explo- ration of the programming process, using such tools as top-down design and object-oriented design. Over time, our understanding of the role of abstract data types and their implementations matured. The operating system, with its resource-management techniques—including files on ever-larger, faster secondary storage media—developed to surround and manage these programs. The next layer of the computer system “onion” is composed of sophisticated general-purpose and special-purpose software systems that xix  xx Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images ­ verlay the operating system. Development of these powerful programs o was stimulated by theoretical work in computer science, which makes such programs possible. The final layer comprises networks and network software—that is, the tools needed for computers to communicate with one another. The Internet and the World Wide Web put the finishing touches to this layer, and this text culminates with a discussion of security issues affecting our interaction online. As these layers have grown over the years, the user has become increasingly insulated from the computer system’s hardware. Each of these layers provides an abstraction of the computing system beneath it. As each layer has evolved, users of the new layer have joined with users of inner layers to create a very large workforce in the high-tech sector of Information Layer the global economy. This book is designed Hardware Layer Programming Layer to provide an overview of the layers, Operating Systems Layer introducing the underlying hardware Applications Layer and software technologies, in order Communications Layer to give students an appreciation and understanding of all aspects of com- puting systems. Having used history to describe the formation of the onion from the inside out, we were faced with a design choice: We could look at each layer in depth from the inside out or the outside in. The outside-in approach was very tempt- ing. We could peel the layers off one at a time, moving from the most abstract layer to the con- crete machine. However, research has shown that students understand concrete examples more easily than abstract ones, even when the students themselves are abstract thinkers. Thus, we have chosen to begin with the concrete machine and examine the layers in the order in which they were created, trusting that a thorough understanding of one layer makes the transition to the next abstraction easier for the students.  xxi Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Changes in the Seventh Edition As always when planning a revision, we asked our colleagues, including many current users of the text, to give us feedback. We appreciate the many thoughtful and insightful responses we received. A variety of changes have been made throughout the book with the Seventh Edition. One includes a conscious effort to improve our coverage of the specific topics described in the AP Computer Science Principles cur- riculum. This book was already a good match for that approach, but the curriculum provided a wealth of ideas for updated content, both large and small. An overview of the Big Ideas in computing that form the high-level framework of the Principles curriculum is now included in Chapter 1. Among the other larger changes with this edition are a stronger introduction to cloud computing, an updated example computer spec- ification described in Chapter 5, a discussion of spreadsheet visualiza- tion and an introduction to big data in Chapter 12, a discussion of smart speakers such as Amazon Echo and Google Home in Chapter 13, a dis- cussion of blockchain in Chapter 15, and updated security discussions in Chapter 17. Another big change in the Seventh Edition is a complete overhaul of Chapter 6 to update the text and examples to use the Pep/9 machine. Sev- eral improvements were made to the underlying system in the upgrade from Pep/8 that help the explanations of programming at the machine- language and assembly levels. In addition, the special features throughout the book have been com- pletely revised and augmented. The “Ethical Issues” sections at the end of each chapter have been brought up to date, addressing the ever-changing state of those issues. Several additional “Did You Know?” sidebars have been added and many others updated. Finally, the biographical sketches throughout the book have been updated. As with each edition, the entire text has been reviewed for opportu- nities to improve the coverage, presentation, and examples used. Updated (and sometimes streamlined) text throughout the book helps to clarify the topics presented. xxii Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Synopsis Chapter 1 lays the groundwork, as described in the “Rationale for This Book’s Organization” section above. Chapters 2 and 3 step back and ­examine a layer that is embodied in the physical hardware. We call this the “information layer” because it reflects how data is represented in the computer. Chapter 2 covers the binary number system and its relation- ship 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 data we manage—numbers, text, images, audio, and video—and repre- sent them in a computer in binary format. Chapters 4 and 5 discuss the hardware layer. Computer hardware includes devices such as transistors, gates, and circuits, all of which control the flow of electricity in fundamental ways. This core electronic circuitry gives rise to specialized hardware components like the computer’s central processing unit (CPU) and memory. Chapter 4 covers gates and electronic circuits; Chapter 5 focuses on the hardware components of a computer and how they interact within a von Neumann architecture. Chapters 6 through 9 examine aspects of the programming layer. Chapter 6 explores the concepts of both machine-language and ­assembly- language programming using Pep/9, a simulated computer. We discuss the functionality of pseudocode as a way to write algorithms. The con- cepts of looping and selection are introduced here, expressed in pseudo- code, and implemented in Pep/9. Chapter 7 examines the problem-solving process as it relates to both humans and computers. George Polya’s human problem-solving strategies guide the discussion. Top-down design is presented as a way to design simple algorithms. We choose classic searching and sorting algorithms as the context for the discussion of algorithms. Because algo- rithms operate on data, we examine ways to structure data so that it can be more efficiently processed. We also introduce subalgorithm (subpro- gram) statements. Chapter 8 explores abstract data types and containers: composite structures for which we know only properties or behaviors. Lists, sorted lists, stacks, queues, binary search trees, and graphs are discussed. The section on subalgorithms is expanded to include reference and value parameters and parameter passing.  xxiii Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Chapter 9 covers the concepts of high-level programming languages. Because many prominent high-level languages include functionality associated with object-oriented programming, we detour and first present this design process. Language paradigms and the compilation process are discussed. Pseudocode concepts are illustrated in brief examples from four programming languages: Python, Visual Basic.NET, C++, and Java. Chapters 10 and 11 cover the operating system layer. Chapter 10 discusses the resource management responsibilities of the operating sys- tem and presents some of the basic algorithms used to implement these tasks. Chapter 11 focuses on file systems, including what they are and how they are managed by the operating system. Chapters 12 through 14 cover the application layer. This layer is made up of the general-purpose and specialized application programs that are available to the public for solving programs. We divide this layer into the sub-disciplines of computer science upon which these programs are based. Chapter 12 examines information systems, Chapter 13 exam- ines artificial intelligence, and Chapter 14 examines simulation, graphics, gaming, and other applications. Chapters 15 through 17 cover the communication layer. Chapter 15 presents the theoretical and practical aspects of computers communicat- ing with each other. Chapter 16 discusses the World Wide Web and the various technologies involved. Chapter 17 examines computer security and keeping information protected in the modern information age. Chapters 2 through 17 are about what a computer can do and how. Chapter 18 concludes the text with a discussion of the inherent limita- tions of computer hardware and software, including the problems that can and cannot be solved using a computer. We present Big-O notation as a way to talk about the efficiency of algorithms so that the categories of algorithms can be discussed, and we use the halting problem to show that some problems are unsolvable. The first and last chapters form bookends: Chapter 1 describes what a computing system is and Chapter 18 cautions about what a computing system is not. The chapters between take an in-depth look at the layers that make up a computing system. xxiv Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Why Not a Language? Instead of championing a specific programming language such as Java, C++, or something else, we decided to leave the choice to the user. Intro- ductory chapters, formatted in a manner consistent with the design of this book, are available for Java, C++, JavaScript, Visual Basic. NET, Python, SQL, Ruby, Perl, Alice, and Pascal on the book’s website. If the students have enough knowledge and experience to master the introductory syntax and semantics of a language in addition to the background material in this book, simply have the students download the appropriate chapter. As an alternative, one or all of these chapters can be used to enrich the studies of those who have stronger backgrounds. 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. 349 Biographies 10.4 CPU Scheduling Each chapter includes a short biogra- © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images phy of someone who has made a signif- Steve Jobs icant contribution to computing as we Born in 1955, Steve Jobs is probably best known for founding Apple Computer together Having been ousted from the company he founded, Jobs began know it. The people honored in these with Steve Wozniak and Ronald Wayne in 1976. At the time, most computers were either another computer company, NeXT, which was purchased by Apple in sections range from those who contrib- © Christophe Ena/AP Photos mainframes (sometimes as large as a small room) or minicomputers (about the size of a 1996 for $402 million. Not only did the acquisition bring Jobs back to his original uted to the data layer, such as George refrigerator), often anything but user-friendly, and almost exclusively used by big businesses. company, but it also made him CEO of Apple. Under his renewed leadership, Apple launched Boole and Ada Lovelace, to those who Jobs had a vision of a personal computer that the iMac, which has been described as the “gold would be accessible to everyone. He is often standard of desktop computing.” have contributed to the communication credited with democratizing the computer. In 1986, Jobs moved into the field of com- Jobs and Wozniak designed the Apple I in puter-generated animation when he bought layer, such as Doug Engelbart and Tim Jobs’s bedroom and built it in the garage of his a computer graphics company and renamed parents’ house. Jobs and Wozniak sold their it Pixar. Pixar has produced a number of box Berners-Lee. These biographies give ­ prize possessions (a Volkswagen microbus and office hits, including A Bug’s Life, Toy Story, a Hewlett-Packard scientific calculator, respec- Monsters, Inc., and Finding Nemo. students a taste of history and introduce tively) to raise the $1300 capital with which Jobs, himself a university dropout, gave they founded their company. Four years later, Apple went public. At the end of the first day the 2005 commencement address at Stanford University, in which he imparted the following them to the men and women who are of trading, the company had a market value of $1.2 billion. piece of career advice to the graduates: “You’ve got to find what you love.” pioneers in the world of computing. Jobs headed the team that developed the In 2007 Jobs was named the most power- Apple Macintosh (named after the McIntosh ful person in business by Fortune magazine, and apple), perhaps the most famous of the Apple Governor Arnold Schwarzenegger inducted computers. The Macintosh was the first com- Jobs into the California Hall of Fame. In August mercially successful computer to be launched 2011 Jobs resigned as CEO of Apple; he was with a graphical user interface and a mouse. elected Chairman of the Board. Tim Cook took Shortly after the launch of the Macintosh, Jobs over as CEO of Apple. After battling pancreatic was forced out of Apple after a power struggle cancer, Steve Jobs died on October 5, 2011, at with John Sculley, Apple’s CEO at the time. the age of 56. Note that the round-robin algorithm is preemptive. The expiration of a time slice is an arbitrary reason to remove a process from the CPU. This  xxv Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Did You Know ? Virtual games and Our second feature (the “Did You Know?” sections indicated by national security a question mark) comprises sidebars that include interesting tid- bits of information from the past, present, and future. They are U.S. and British spies have infiltrated the garnered from history, current events, and the authors’ personal fantasy world of virtual experiences. These little vignettes are designed to amuse, inspire, games. A 2008 National intrigue, and, of course, educate. Security Agency (NSA) document declared that virtual games Ethical Issues provide a “target- rich communication Our third feature is an “Ethical Issues” section that is included network” that allows A in each chapter. These sections illustrate the fact that along with intelligence suspects a way to communicate the advantages of computing come responsibilities for and con- and “hide in plain sequences of its use. Privacy, hacking, viruses, and free speech sight.”4 are among the topics discussed. Following the exercises in each 49 chapter, a “Thought Questions” Key Terms section asks stimulating questions A about these ethical issues as well ETHICAL ISSUES as ­chapter ­content. The FISA Court The United States Foreign Intelligence Sur- the U.S. Attorney General determines that an Color and veillance Court is a U.S. federal court that emergency exists, he or she may authorize was established under the Foreign Intel- the electronic surveillance but must notify a ligence Surveillance Act of 1978 (FISA). Court judge not more than 72 hours after the The Court handles requests by federal law authorization. The USA PATRIOT Act of 2001 Typography Are enforcement agencies for surveillance war- rants against suspected foreign intelligence agents operating inside the United States.4 expanded the time periods during which sur- veillance may be authorized.5 In December 2012, President Obama Signposts Before 2013, when Edward Snowden signed the FISA Amendments Act Reau- leaked that the Court had ordered a subsidi- thorization Act of 2012, which extended ary of Verizon to provide detailed call records Title VII of FISA until December 31, 2017. to the National Security Agency (NSA), most In January, 2018, President Trump reau- people had never heard of the FISA Court. thorized it again through 2023. The layers into which the book The FISA Court comprises 11 judges who Title VII of FISA, added by the FISA sit for 7-year terms. The Chief Justice of the Amendments Act of 2008, created separate is divided are color coded within Supreme Court appoints the judges, without procedures for targeting suspected foreign confirmation. An application for an elec- intelligence agents, including non-U.S. per- the text. The opening spread for tronic surveillance warrant is made before sons and U.S. persons reasonably believed one of the judges. The court may amend this to be outside the United States.6 each chapter shows an image of application before granting the warrant. If the application is denied, the government may Note that the stated intent of the FISA Court is to protect the United States as well the onion in which the outermost not take the same request to another judge. If as the rights of U.S. citizens. color corresponds to the current layer. This color is repeated in header bars and KEYsection TERMS numbers through- out the layer. Each opening spread also visuallyBase indicates where the chap- Negative number ter is within the layer and the book. Binary digit Bit Number Positional notation We have said that the first and last chapters Byte form bookends. Although Integer Rational number Word Natural number they are not part of the layers of the computing onion, these chapters are xxvi Preface © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images color coded like the others. Open the book anywhere and you can imme- diately tell where you are within the layers of computing. To visually separate the abstract from the concrete in the program- ming layer, we use different fonts for algorithms, including identifiers in running text, and program code. You know at a glance whether the discussion is at the logical (algorithmic) level or at the programming-­ language level. In order to distinguish visually between an address and the contents of an address, we color addresses in orange. Color is especially useful in Chapter 6, “Low-Level Programming Lan- guages and Pseudocode.” Instructions are color coded to differentiate the parts of an instruction. The operation code is blue, the register designa- tion is clear, and the addressing mode specifier is green. Operands are shaded gray. As in other chapters, addresses are in orange. Instructor Resources For the instructor, slides in PowerPoint format, a test bank, and answers to the book’s end-of-chapter exercises are available for free download at http://go.jblearning.com/CSI7e. ACKNOWLEDGMENTS © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Our adopters have been most helpful during this revision. To those who took the time to respond to our online survey: Thanks to all of you. We are also grateful to the reviewers of the previous editions of the text: Warren W. Sheaffer, Saint Paul College Tim Bower, Kansas State University Terri Grote, St. Louis Community College Susan Glenn, Gordon State College Simon Sultana, Fresno Pacific University Shruti Nagpal, Worcester State University Sandy Keeter, Seminole State College of Florida S. Monisha Pulimood, The College of New Jersey Roy Thelin, Ridge Point High School Robert Yacobellis, Loyola University Chicago Richard Croft, Eastern Oregon University Raymond J. Curts, George Mason University Mia Moore, Clark Atlanta University Melissa Stange, Lord Fairfax Community College Matthew Hayes, Xavier University of Louisiana Marie Arvi, Salisbury University Linda Ehley, Alverno College Keson Khieu, Sierra College Keith Coates, Drury University Joon Kim, Brentwood School Joe Melanson, Corning Painted Post Joan Lucas, College at Brockport, State University of New York Jeffrey L. Lehman, Huntington University Janet Helwig, Dominican University James Thomas Davis, A. Crawford Mosley High School James Hicks, Los Angeles Southwest College Jacquilin Porter, Henry Ford College and Baker College Homer Sharafi, Northern Virginia Community College Gil Eckert, Monmouth University Gary Monnard, St. Ambrose University David Klein, Hofstra University David Adams, Grove City College Christopher League, LIU Brooklyn xxvii xxviii Acknowledgments © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Carol Sweeney, Villa Maria Academy High School Brian Bradshaw, Thiel College Bill Cole, Sierra College-Rocklin Aparna Mahadev, Worcester State University Anna Ursyn, UNC Colorado Ann Wojnar, Beaumont School Special thanks to Jeffrey McConnell of Canisius College, who wrote the graphics section in Chapter 14; Herman Tavani of Rivier College, who helped us revise the “Ethical Issues” sections; Richard Spinello of Boston College for his essay on the ethics of blogging; and Paul Toprac, Associate Director of Game Development at The University of Texas at Austin, for his contributions on gaming. We appreciate and thank our reviewers and colleagues who provided advice and recommendations for the content in this Seventh Edition: Tim Bower, Kansas State University Brian Bradshaw, Thiel College Keith Coates, Drury University Raymond J. Curts, George Mason University James Thomas Davis, A. Crawford Mosley High School Gil Eckert, Monmouth University Susan Glenn, Gordon State College Terri Grote, St. Louis Community College Matthew Hayes, Xavier University of Louisiana Sandy Keeter, Seminole State College of Florida Keson Khieu, Sierra College Joon Kim, Brentwood School David Klein, Hofstra University Christopher League, LIU Brooklyn Jeffrey L. Lehman, Huntington University Joan Lucas, College at Brockport, State University of New York Joe Melanson, Corning Painted Post Gary Monnard, St. Ambrose University Shruti Nagpal, Worcester State University Jacquilin Porter, Henry Ford College and Baker College Homer Sharafi, Northern Virginia Community College  xxix Acknowledgments © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Melissa Strange, Lord Fairfax Community College Simon Sultana, Fresno Pacific University Carol Sweeney, Villa Maria Academy High School Roy Thelin, Ridge Point High School Anna Ursyn, UNC Colorado Ann Wojnar, Beaumont School We also thank the many people at Jones & Bartlett Learning who contrib- uted so much, especially Laura Pagluica, Director of Product Management; Loren-Marie Durr, Product Assistant; and Alex Schab, Project Specialist. I must also thank my tennis buddies for keeping me fit, my bridge buddies for keeping my mind alert, and my family for keeping me grounded. —ND I’d like to thank my family for their support. —JL SPECIAL FEATURES © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Interspersed throughout Computer Science Illuminated, Seventh Edition, are two special features of note: Ethical Issues and Biographies. A list of each is provided below for immediate access. ETHICAL ISSUES Digital Divide (Chapter 1, p. 30) The FISA Court (Chapter 2, p. 49) The Fallout from Snowden’s Revelations (Chapter 3, p. 86) Codes of Ethics (Chapter 4, p. 114) Is Privacy a Thing of the Past? (Chapter 5, p. 146) Software Piracy (Chapter 6, p. 185) Open-Source Software (Chapter 7, p. 232) Workplace Monitoring (Chapter 8, p. 273) Hoaxes and Scams (Chapter 9, p. 321) Medical Privacy: HIPAA (Chapter 10, p. 352) Privacy: Opt-In or Opt-Out? (Chapter 11, p. 380) Politics and the Internet (Chapter 12, p. 411) Initial Public Offerings (Chapter 13, p. 447) Gaming as an Addiction (Chapter 14, p. 489) The Effects of Social Networking (Chapter 15, p. 519) Gambling and the Internet (Chapter 16, p. 551) Blogging and Journalism (Chapter 17, p. 580) Therac-25: Anatomy of a Disaster (Chapter 18, p. 620) xxx  xxxi Special Features © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images BIOGRAPHIES Ada Lovelace, the First Programmer (Chapter 1, p. 14) Grace Murray Hopper (Chapter 2, p. 46) Bob Bemer (Chapter 3, p. 72) George Boole (Chapter 4, p. 95) John Vincent Atanasoff (Chapter 5, p. 127) Konrad Zuse (Chapter 6, p. 181) George Polya (Chapter 7, p. 195) John von Neumann (Chapter 8, p. 248) Edsger Dijkstra (Chapter 9, p. 309) Steve Jobs (Chapter 10, p. 349) Tony Hoare (Chapter 11, p. 377) Daniel Bricklin (Chapter 12, p. 395) Herbert A. Simon (Chapter 13, p. 424) Ivan Sutherland (Chapter 14, p. 462) Doug Engelbart (Chapter 15, p. 503) Tim Berners-Lee (Chapter 16, p. 538) Mavis Batey (Chapter 17, p. 576) Alan Turing (Chapter 18, p. 613) Laying the Groundwork 1 The Big Picture The Information Layer 2 Binary Values and Number Systems 3 Data Representation The Hardware Layer 4 Gates and Circuits 5 Computing Components The Programming Layer 6 Low-Level Programming Languages and Pseudocode 7 Problem Solving and Algorithms 8 Abstract Data Types and Subprograms 9 Object-Oriented Design and High-Level Programming Languages The Operating Systems Layer 10 Operating Systems 11 File Systems and Directories The Applications Layer 12 Information Systems 13 Artificial Intelligence 14 Simulation, Graphics, Gaming, and Other Applications The Communications Layer 15 Networks 16 The World Wide Web 17 Computer Security In Conclusion 18 Limitations of Computing LAYING THE GROUNDWORK  1 THE BIG PICTURE This book is a tour through the world of computing. We explore how com- puters 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 dif- ferent elements, which combine 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. Hardware, software, programming, web surfing, and email are prob- ably 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 establishing common terminology and creating the plat- form from which we will dive into our exploration of computing. GOALS After studying this chapter, you should be able to: describe the layers of a computer system. describe the concept of abstraction and its relationship to computing. describe the history of computer hardware and software. describe the changing role of the computer user. distinguish between systems programmers and applications programmers. distinguish between computing as a tool and computing as a discipline. 3  4 Chapter 1: The Big Picture Computing system 1.1 Computing Systems Computer hardware, software, and data, In this book we explore various aspects of computing systems. Note that which interact to we use the term computing system, not just computer. A computer is a solve problems device. A computing system, by contrast, is a dynamic entity, used to solve problems and interact with its environment. A computing sys- Computer hardware The physical elements tem is composed of hardware, software, and the data that they manage. of a computing Computer hardware is the collection of physical elements that make up system the machine and its related pieces: boxes, circuit boards, chips, wires, disk drives, keyboards, monitors, printers, and so on. Computer software Computer software is the collection of programs that provide the instructions that a com- The programs that provide the puter carries out. And at the very heart of a computer system is the instructions that a information that it manages. Without data, the hardware and software computer executes are essentially useless. The general goals of this book are threefold: To give you a solid, broad understanding of how a computing system works To help you develop an appreciation for and understanding of the evolution of modern computing systems To give you enough information about computing so that you can decide whether you wish to pursue the subject further The rest of this section explains how computer systems can be divided into abstract layers and how each layer plays a role. The next section puts the development of computing hardware and software into histori- cal context. This chapter concludes with a discussion about computing as both a tool and a discipline of study. Layers of a Computing System A computing system is like an onion, made up of many layers. Each layer plays a specific role in the overall design of the system. These layers are depicted in FIGURE 1.1 and form the general organization of this book. This is the “big picture” that we will continually return to as we explore different aspects of computing systems. You rarely, if ever, take a bite out of an onion as you would an apple. Rather, you separate the onion into concentric rings. Likewise, in this book we explore aspects of computing one layer at a time. We peel each layer separately and explore it by itself. Each layer, in itself, is not that com­­­­plicated. In fact, a computer actually does only very simple tasks—it just does them so blindingly fast that many simple tasks can be combined  5 1.1 Computing Systems to accomplish larger, more complicated tasks. Communications When the various computer layers are all brought together, each playing its own role, amazing things Applications result from the combination of these basic ideas. Operating systems Let’s discuss each of these layers briefly and Programming identify where in this book these ideas are explored in more detail. We essentially work our way from Hardware the inside out, which is sometimes referred to as a Information bottom-up approach. The innermost layer, information, reflects the way we represent information on a computer. In many ways this is a purely conceptual level. Infor- mation on a computer is managed using binary FIGURE 1.1 The layers of a computing system digits, 1 and 0. So to understand computer pro- cessing, we must first understand the binary number system and its rela- tionship to other number systems (such as the decimal system, the one humans use on a daily basis). Then we can turn our attention to how we take the myriad types of information we manage—numbers, text, images, audio, and video—and represent them in a binary format. Chapters 2 and 3 explore these issues. The next layer, hardware, consists of the physical hardware of a com- puter system. Computer hardware includes devices such as gates and cir- cuits, which control the flow of electricity in fundamental ways. This core electronic circuitry gives rise to specialized hardware components such as the computer’s central processing unit (CPU) and memory. Chapters 4 and 5 of the book discuss these topics in detail. The programming layer deals with software, the instructions used to accomplish computations and manage data. Programs can take many forms, be performed at many levels, and be implemented in many lan- guages. Yet, despite the enormous variety of programming issues, the goal remains the same: to solve problems. Chapters 6 through 9 explore many issues related to programming and the management of data. Every computer has an operating system (OS) to help manage the computer’s resources. Operating systems, such as Windows, Mac OS, or Linux, help us interact with the computer system and manage the way hardware devices, programs, and data interact. Knowing what an operat- ing system does is key to understanding the computer in general. These issues are discussed in Chapters 10 and 11. The previous (inner) layers focus on making a computer system work. The applications layer, by contrast, focuses on using the computer to solve specific real-world problems. We run application programs to  6 Chapter 1: The Big Picture take ­advantage of the computer’s abilities in other areas, such as helping us design a building or play a game. The spectrum of area-specific com- puter software tools is far-reaching and involves specific subdisciplines of computing, such as information systems, artificial intelligence, and simu- lation. Application systems are discussed in Chapters 12, 13, and 14. Of course, computers no longer exist in isolation on someone’s desktop. We use computer technology to communicate, and that com- munication is a fundamental layer at which computing systems oper- ate. Computers are connected into networks so that they can share information and resources. The Internet evolved into a global network, ­ so there is now almost no place on Earth you can’t reach with comput- ing technology. The World Wide Web makes that communication easier; it has revolutionized computer use and made it accessible to the general public. Cloud computing is the idea that our computing needs can be han- dled by resources at various places on the Internet (in the cloud), rather than on local computers. Chapters 15 and 16 discuss these important issues of computing communication. The use of computing technology can result in increased security haz- ards. Some issues of security are dealt with at low levels throughout a computer system. Many of them, though, involve keeping our personal information secure. Chapter 17 discusses several of these issues. Most of this book focuses on what a computer can do and how it does it. We conclude the book with a discussion of what a computer cannot do, or at least cannot do well. Computers have inherent limitations on their ability to represent information, and they are only as good as their pro- gramming makes them. Furthermore, it turns out that some problems can- not be solved at all. Chapter 18 examines these limitations of computers. Sometimes it is easy to get so caught up in the details that we lose perspective on the big picture. Try to keep that in mind as you pro- gress through the information in this book. Each chapter’s opening page reminds you of where we are in the various layers of a computing system. The details all contribute a specific part to a larger whole. Take each step in turn and you will be amazed at how well it all falls into place. Abstraction The levels of a computing system that we just examined are examples of abstraction. An abstraction is a mental model, a way to think about some- Abstraction A mental thing, that removes or hides complex details. An abstraction includes the model that removes information necessary to accomplish our goal, but leaves out information complex details that would unnecessarily complicate matters. When we are dealing with  7 1.1 Computing Systems a computer on one layer, we don’t need to be thinking about the details of the other layers. For example, when we are writ- ing a program, we don’t have to concern ourselves with how the hardware carries out the instructions. Likewise, when we are running an application program, we don’t have to be con- cerned with how that program was written. Numerous experiments have shown that a human being can actively manage about seven (plus or minus two, depend- ing on the person) pieces of information in short-term mem- ory at one time. This is called Miller’s Law, based on the psychologist who first investigated it.1 Other pieces of infor- mation are available to us when we need them, but when we focus on a new piece, something else falls back into second- ary status. This concept is similar to the number of balls a juggler can Reprinted by permission of Dan Piraro. Visit, https://bizarro.com/ keep in the air at one time. Human beings can mentally juggle about seven balls at once, and when we pick up a new one, we have to drop another. Seven may seem like a small number, but the key is that each ball can represent an abstraction, or a chunk of information. That is, each ball we are juggling can represent a complex topic as long as we can think about it as one idea. We rely on abstractions every day of our lives. For example, we don’t need to know how a car works to drive one to the store. That is, we don’t really need to know how the engine works in detail. We need to know only some basics about how to interact with the car: how the pedals and knobs and steering wheel work. And we don’t even have to be thinking about all of those things at the same time. See FIGURE 1.2. FIGURE 1.2 A car engine and the abstraction that allows us to use it © aospan/Shutterstock; © Syda Productions/Shutterstock  8 Chapter 1: The Big Picture Even if we do know how an engine works, we don’t have to think Information hiding A technique for about it while driving. Imagine if, while driving, we had to constantly isolating program think about how the spark plugs ignite the fuel that drives the pistons that pieces by eliminating turn the crankshaft. We’d never get anywhere! A car is much too compli- the ability for one cated for us to deal with all at once. All the technical details would be too piece to access many balls to juggle at the same time. But once we’ve abstracted the car the information in down to the way we interact with it, we can deal with it as one entity. The another irrelevant details are ignored, at least for the moment. Information hiding is a concept related to abstraction. A computer programmer often tries to eliminate the need or ability of one part of a program to access information located in another part. This technique keeps the pieces of the program isolated from each other, which reduces errors and makes each piece easier to understand. Abstraction focuses on the external view—the way something behaves and the way we interact with it. Information hiding is a design feature that gives rise to the abstractions that make something easier to work with. Information hiding and abstraction are two sides of the same coin. Abstract art, as the term implies, is another example of abstraction. An abstract painting represents something but doesn’t get bogged down in the details of reality. Consider the painting shown in FIGURE 1.3 , entitled Nude Descending a Staircase. You can see only the basic hint of the woman and the staircase, because the artist is not interested in the details of exactly how the woman or the stair- case looks. Those details are irrelevant to the effect the artist is trying to create. In fact, the realistic details would get in the way of the issues that the artist thinks are important. Abstraction is the key to computing. The layers of a computing system ­embody the idea of abstraction. And abstractions keep appearing within i­ ndividual layers in various ways as well. In fact, abstraction can be seen throughout the entire evo- FIGURE 1.3 Marcel Duchamp discussing his abstract painting Nude Descending a Staircase lution of computing systems, which we © CBS/Landov explore in the next section.  9 1.2 The History of Computing 1.2 The History of Computing The historical foundation of computing goes a long way toward explain- ing why computing systems today are designed as they are. Think of this section as a story whose characters and events have led to the place we are now and form the foundation of the exciting future to come. We examine the history of computing hardware and software separately because each has its own impact on how computing systems evolved into the layered model we use as the outline for this book. This history is written as a narrative, with no intent to formally define the concepts discussed. In subsequent chapters, we return to these con- cepts and explore them in more detail. A Brief History of Computing Hardware The devices that assist humans in various forms of computation have their roots in the ancient past and have continued to evolve until the present day. Let’s take a brief tour through the history of computing hardware. Early History Many people believe that Stonehenge, the famous collection of rock monoliths in Great Britain, is an early form of a calendar or astrological calculator. The abacus, which appeared in the sixteenth century bc, was developed as an instrument to record numeric values and on which a ? Beyond all dreams human can perform basic arithmetic. In the middle of the seventeenth century, Blaise Pascal, a French “Who can foresee mathematician, built and sold gear-driven mechanical machines, which the consequences of performed whole-number addition and subtraction. Later in the seven- such an invention? teenth century, a German mathematician, Gottfried Wilhelm von Leibniz, The Analytical Engine built the first mechanical device designed to do all four whole-number weaves algebraic patterns just as the operations: addition, subtraction, multiplication, and division. Unfortu- Jacquard loom weaves nately, the state of mechanical gears and levers at that time was such that flowers and leaves. the Leibniz machine was not very reliable. The engine might In the late eighteenth century, Joseph Jacquard developed what became compose elaborate known as Jacquard’s loom, used for weaving cloth. The loom used a series and scientific pieces of music of any degree of of cards with holes punched in them to specify the use of specific colored complexity or extent.” thread and therefore dictate the design that was woven into the cloth. —Ada, Countess of ­Although not a computing device, Jacquard’s loom was the first to make Lovelace, 18432 use of what later became an important form of input: the punched card.  10 Chapter 1: The Big Picture © Artur Debat/Getty Images; © Alan Dyer/Stocktrek Images/Getty Images Stonehenge Is Still a Mystical Place Stonehenge, a Neolithic stone structure that used as an astro- rises majestically out of the Salisbury Plain in nomical calendar, England, has fascinated humans for centuries. marking lunar It is believed that Stonehenge was erected over and ­ solar align- several centuries beginning in about 2180 bce. ments. Yet a third vencacolrab/iStock/Thinkstock Its purpose is still a mystery, ­ although theo- the­­ory is that ries abound. At the summer solstice, the rising Stonehenge was used to predict ­eclipses. Later sun appears behind one of the main stones, research showed that Stonehenge was also used giving the illusion that the sun is balancing as a cemetery.3 Human remains, from about on the stone. This has led to the early theory 3000 bce until 2500 bce when the first large that Stonehenge was a temple. Another theory, stones were raised, have been found. Regardless first suggested in the middle of the twentieth of why it was built, there is a mystical quality century, is that Stonehenge could have been about the place that defies explanation. It wasn’t until the nineteenth century that the next major step was taken in computing, this time by a British mathematician. Charles Bab- bage designed what he called his analytical engine. His design was too com- plex for him to build with t