Computer Science - Pearson

1 13th EditionJ. Glenn Brookshear(Author Emeritus)andDennis BrylowMarquette University330 Hudson Street, NY NY 10013 Computer ScienceAN 12/6/18 5:04 PMSenior Vice President, Courseware Portfolio Management: Engineering, Computer Science , Mathematics, Statistics, and Global Editions: Marcia HortonDirector, Portfolio Management: Engineering, Computer Science , and Global Editions: Julian PartridgeExecutive Portfolio Manager: Tracy JohnsonPortfolio Management Assistant: Meghan JacobyManaging Producer, ECS and Mathematics: Scott DisannoSenior Content Producer: Erin AultManager, Rights and Permissions Manager: Ben FerriniOperations Specialist: Maura Zaldivar-GarciaInventory Manager: Bruce BountyProduct Marketing Manager: Yvonne VannattaField Marketing Manager: Demetrius HallMarketing Assistant: Jon BryantFull Service Project Management: Sasibalan Chidambaram, SPi GlobalComposition: SPi GlobalCover Design: Black Horse DesignsCover Photo: wacomka/ShutterstockCover Printer: Phoenix Color/HagerstownPrinter/Binder: Lake Side Communications, Inc.

2 (LSC)Typeface: Times Ten LT StdCopyright 2019, 2014, 2013, 2010 by Pearson Education, Inc., Hoboken, NJ 07030. All rights in the United States of America. This publication is protected by copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise. For information regarding permissions, request forms and the appropriate contacts within the Pearson Education Global Rights & Permissions department, please visit of the designations by manufacturers and seller to distinguish their products are claimed as trademarks.

3 Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these Data is on file at the Library of CongressISBN-10: 0-13-487546-XISBN-13: 978-0-134-87546-01 22/6/18 5:04 PMFor Dexter,who I know will eagerly readthis book cover to coverbefore he turns , the places you will go.

4 32/6/18 5:04 PM ivContents Chapter 0 Introduction 3 The Role of Algorithms 4 The History of Computing 6 An Outline of Our Study 11 The Overarching Themes of Computer Science 13 Chapter 1 Data Storage 25 Bits and Their Storage 26 Main Memory 34 Mass Storage 37 Representing Information as Bit Patterns 43 * The Binary System 51 * Storing Integers 56 * Storing Fractions 63 * Data and Programming 69 * Data Compression 77 * Communication Errors 83 Chapter 2 Data Manipulation 97 Computer Architecture 98 Machine Language 101 Program Execution 108 * Arithmetic/Logic Instructions 116 * Communicating with Other Devices 121 * Programming Data Manipulation 126 * Other

5 Architectures 137 Chapter 3 Operating Systems 149 The History of Operating Systems 150 Operating System Architecture 155 Coordinating the Machine s Activities 163 * Handling Competition Among Processes 166 Security 172 Chapter 4 Networking and the Internet 183 Network Fundamentals 184 The Internet 194 The World Wide Web 206* Asterisks indicate suggestions for optional 42/6/18 5:04 PM vContents * Internet Protocols 215 * Simple Client Server 223 Cybersecurity 227 Chapter 5 Algorithms 245 The Concept of an Algorithm 246 Algorithm Representation 249 Algorithm Discovery 258 Iterative Structures 265 Recursive Structures 276 Efficiency and Correctness 285 Chapter 6 Programming Languages 305 Historical Perspective 306 Traditional Programming Concepts 317 Procedural Units 332 Language Implementation 340 Object-Oriented Programming 350 * Programming Concurrent Activities 357 * Declarative Programming 360 Chapter 7 Software Engineering 375 The Software Engineering Discipline 376 The Software Life Cycle 379 Software Engineering

6 Methodologies 384 Modularity 387 Tools of the Trade 396 Quality Assurance 405 Documentation 408 The Human-Machine Interface 410 Software Ownership and Liability 414 Chapter 8 Data Abstractions 423 Basic Data Structures 424 Related Concepts 429 Implementing Data Structures 432 A Short Case Study 447 Customized Data Types 452 Classes and Objects 456 * Pointers in Machine Language 458 Chapter 9 Database Systems 471 Database Fundamentals 472 The Relational Model 52/6/18 5:04 PM viContents * Object-Oriented Databases 489 * Maintaining Database Integrity 492 * Traditional File Structures 496 Data Mining 505 Social Impact of Database Technology 508 Chapter 10 Computer Graphics 519 The Scope of Computer Graphics 520 Overview of 3D Graphics 523 Modeling 525 Rendering 535 * Dealing with Global Lighting 547 Animation 550 Chapter 11 Artificial Intelligence 561 Intelligence and Machines 562 Perception 567 Reasoning 574 Additional Areas of Research 586 Artificial Neural Networks 593 Robotics 598 Considering the Consequences 601 Chapter 12 Theory of Computation 615 Functions and Their Computation 616 Turing

7 Machines 619 Universal Programming Languages 623 A Noncomputable Function 629 Complexity of Problems 634 * Public-Key Cryptography 646 Appendixes 656 A ASCII 656 B Circuits to Manipulate Two s Complement Representations 657 C Vole: A Simple Machine Language 660 D High-Level Programming Languages 663 E The Equivalence of Iterative and Recursive Structures 665 F Answers to Questions & Exercises 667 Index 62/6/18 5:04 PM viiPrefaceThis book presents an introductory survey of Computer Science . It explores the breadth of the subject while including enough depth to convey an honest appreciation for the topics wrote this text for students of Computer Science as well as students from other disciplines.

8 As for Computer Science students, most begin their studies with the illusion that Computer Science is programming, web browsing, and Internet file sharing because that is essentially all they have seen. Yet Computer Science is much more than this. Beginning Computer Science students need exposure to the breadth of the subject in which they are planning to major. Providing this exposure is the theme of this book. It gives students an overview of Computer Science a foundation from which they can appreciate the rele-vance and interrelationships of future courses in the field. This survey approach is, in fact, the model used for introductory courses in the natural broad background is also what students from other disciplines need if they are to relate to the technical society in which they live.

9 A Computer Science course for this audience should provide a practical, realistic understanding of the entire field rather than merely an introduction to using the Internet or training in the use of some popular software packages. There is, of course, a proper place for that training, but this text is about writing previous editions of this text, maintaining accessibility for nontechnical students was a major goal. The result was that the book has been used successfully in courses for students over a wide range of disciplines and educational levels, ranging from high school to graduate courses. This 13th edition is designed to continue that in the 13th EditionNow in color! The move to a full color printing process in the 13th edition has allowed us to make many figures and diagrams more descriptive, and to use syntax coloring to better effect for clarifying code and pseudocode segments in the text.

10 Most modern programming interfaces use color to aid the program-mer s understanding of code; your Computer Science textbook should do no major theme during the development of this 13th edition has been highlighting the intersections with the new College Board Advanced Placement Computer Science Principles ( CSP ) exam. This breadth-first textbook for introducing Computer Science has included many of the big ideas and computational practices codified in the CSP framework since long before that exam came into existence; prior editions of the book have been used in 72/6/18 5:04 PM viiiPrefacepilot versions of CSP courses, and as a professional development resource for educators preparing to teach the high school version of the course.