Computing handbook

Computing Handbook, Third Edition: Computer Science and

Software Engineering mirrors the modern taxonomy of computer

science and software engineering as described by the Association for

Computing Machinery (ACM) and the IEEE Computer Society (IEEE￾CS). Written by established leading experts and influential young re￾searchers, the first volume of this popular handbook examines the el￾ements involved in designing and implementing software, new areas

in which computers are being used, and ways to solve computing

problems. The book also explores our current understanding of soft￾ware engineering and its effect on the practice of software develop￾ment and the education of software professionals.

Like the second volume, this first volume describes what occurs in

research laboratories, educational institutions, and public and private

organizations to advance the effective development and use of com￾puters and computing in today’s world. Research-level survey articles

provide deep insights into the computing discipline, enabling readers

to understand the principles and practices that drive computing edu￾cation, research, and development in the twenty-first century.

Features

• Aligns with the undergraduate curriculum models developed by

the ACM and IEEE-CS

• Describes the fundamental principles of computer science, such

as algorithms and architecture

• Covers contemporary topics in computer science and software

engineering, including graphics, intelligent systems, mobile com￾puting, and agile development

Computer Science

K14311

K14311_Cover.indd 1 3/7/14 12:38 PM

COMPUTING

HANDBOOK

THIRD EDITION

Computer Science and

Software Engineering

COMPUTING

HANDBOOK

THIRD EDITION

Computer Science and

Software Engineering

EDITED BY

Teofilo Gonzalez

University of California

Santa Barbara, California, USA

Jorge Díaz-Herrera

Keuka College

Keuka Park, New York, USA

EDITOR-IN-CHIEF

Allen Tucker

Bowdoin College

Brunswick, Maine, USA

MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy

of the text or exercises in this book. This book’s use or discussion of MATLAB® software or related products does not consti￾tute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB®

software.

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

© 2014 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Version Date: 20140117

International Standard Book Number-13: 978-1-4398-9853-6 (eBook - PDF)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to

publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials

or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material repro￾duced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any

copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any

form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming,

and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copy￾right.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400.

CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been

granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identifica￾tion and explanation without intent to infringe.

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

v

Contents

Preface to the Computing Handbook Set xiii

Preface to Volume I: Computer Science and Software Engineering xv

Acknowledgments xxvii

Editors xxix

Contributors xxxi

Part I Overview of Computer Science

1 Structure and Organization of Computing 1-1

Peter J. Denning

2 Computational Thinking 2-1

Valerie Barr

Part II Algorithms and Complexity

3 Data Structures 3-1

Mark Allen Weiss

4 Basic Techniques for Design and Analysis of Algorithms 4-1

Edward M. Reingold

5 Graph and Network Algorithms 5-1

Samir Khuller and Balaji Raghavachari

6 Computational Geometry 6-1

Marc van Kreveld

7 Complexity Theory......................................................................................... 7-1

Eric W. Allender, Michael C. Loui, and Kenneth W. Regan

8 Formal Models and Computability 8-1

Tao Jiang, Ming Li, and Bala Ravikumar

vi Contents

9 Cryptography 9-1

Jonathan Katz

10 Algebraic Algorithms 10-1

Ioannis Z. Emiris, Victor Y. Pan, and Elias P. Tsigaridas

11 Some Practical Randomized Algorithms and Data Structures 11-1

Michael Mitzenmacher and Eli Upfal

12 Approximation Algorithms and Metaheuristics 12-1

Teofilo F. Gonzalez

13 Combinatorial Optimization 13-1

Vijay Chandru and M.R. Rao

14 Graph Drawing 14-1

Ioannis G. Tollis and Konstantinos G. Kakoulis

15 Pattern Matching and Text Compression Algorithms 15-1

Maxime Crochemore and Thierry Lecroq

16 Distributed Algorithms 16-1

Dan Alistarh and Rachid Guerraoui

Part III Architecture and Organization

17 Digital Logic 17-1

Miriam Leeser and James Brock

18 Memory Systems 18-1

Yoongu Kim and Onur Mutlu

19 Storage Systems 19-1

Alexander Thomasian

20 High-Speed Computer Arithmetic 20-1

Earl E. Swartzlander, Jr.

21 Input/Output Devices and Interaction Techniques 21-1

Ken Hinckley, Robert J.K. Jacob, Colin Ware, Jacob O. Wobbrock,

and Daniel Wigdor

22 Performance Enhancements 22-1

Joseph Dumas

23 Parallel Architectures 23-1

Michael J. Flynn and Kevin W. Rudd

24 Multicore Architectures and Their Software Landscape 24-1

Raphael Poss

25 DNA Computing 25-1

Hieu Bui, Harish Chandranm, Sudhanshu Garg, Nikhil Gopalkrishnan,

Reem Mokhtar, John Reif, and Tianqi Song

Contents vii

Part IV Computational Science and Graphics

26 Computational Electromagnetics 26-1

J.S. Shang

27 Computational Fluid Dynamics 27-1

David A. Caughey

28 Computational Astrophysics 28-1

Jon Hakkila, Derek Buzasi, and Robert J. Thacker

29 Computational Chemistry 29-1

J. Phillip Bowen, Frederick J. Heldrich, Clyde R. Metz, Shawn C. Sendlinger, Neal E.

Tonks, and Robert M. Panoff

30 Computational Biology: The Fundamentals of Sequence-Based

Techniques 30-1

Steven M. Thompson

31 Terrain Modeling for the Geosciences 31-1

Herman Haverkort and Laura Toma

32 Geometric Primitives 32-1

Lee Staff, Gustavo Chávez, and Alyn Rockwood

33 Computer Animation 33-1

Nadia Magnenat Thalmann and Daniel Thalmann

Part V Intelligent Systems

34 Paraconsistent Logic-Based Reasoning for Intelligent Systems 34-1

Kazumi Nakamatsu

35 Qualitative Reasoning 35-1

Kenneth Forbus

36 Machine Learning 36-1

Stephen Marsland

37 Explanation-Based Learning37-1

Gerald DeJong

38 Search 38-1

Danny Kopec, James L. Cox, and Stephen Lucci

39 Planning and Scheduling 39-1

Roman Barták

40 Natural Language Processing 40-1

Nitin Indurkhya

41 Understanding Spoken Language 41-1

Gokhan Tur, Ye-Yi Wang, and Dilek Hakkani-Tür

viii Contents

42 Neural Networks 42-1

Michael I. Jordan and Christopher M. Bishop

43 Cognitive Modeling 43-1

Eric Chown

44 Graphical Models for Probabilistic and Causal Reasoning 44-1

Judea Pearl

Part VI Networking and Communication

45 Network Organization and Topologies 45-1

William Stallings

46 Routing Protocols 46-1

Radia Perlman

47 Access Control 47-1

Sabrina De Capitani di Vimercati, Pierangela Samarati, and Ravi Sandhu

48 Data Compression 48-1

O . Ufuk Nalbantoglu and K. Sayood

49 Localization in Underwater Acoustic Sensor Networks 49-1

Baozhi Chen and Dario Pompili

50 Semantic Web 50-1

Pascal Hitzler and Krzysztof Janowicz

51 Web Search Engines: Practice and Experience 51-1

Tao Yang and Apostolos Gerasoulis

Part VII Operating Systems

52 Process Synchronization and Interprocess Communication 52-1

Craig E. Wills

53 Thread Management for Shared-Memory Multiprocessors 53-1

Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy

54 Virtual Memory 54-1

Peter J. Denning

55 Secondary Storage and Filesystems 55-1

Marshall Kirk McKusick

56 Performance Evaluation of Computer Systems 56-1

Alexander Thomasian

57 Taxonomy of Contention Management in Interconnected Distributed

Systems 57-1

Mohsen Amini Salehi, Jemal Abawajy, and Rajkumar Buyya

Contents ix

58 Real-Time Computing 58-1

Sanjoy Baruah

59 Scheduling for Large-Scale Systems 59-1

Anne Benoit, Loris Marchal, Yves Robert, Bora Uçar, and Frédéric Vivien

60 Distributed File Systems 60-1

Thomas W. Doeppner

61 Mobile Operating Systems 61-1

Ralph Morelli and Trishan de Lanerolle

62 Service-Oriented Operating Systems 62-1

Stefan Wesner, Lutz Schubert, and Daniel Rubio Bonilla

Part VIII Programming Languages

63 Imperative Language Paradigm 63-1

Michael J. Jipping and Kim Bruce

64 Object-Oriented Language Paradigm 64-1

Raimund K. Ege

65 Logic Programming and Constraint Logic Programming 65-1

Jacques Cohen

66 Multiparadigm Languages 66-1

Michael Hanus

67 Scripting Languages 67-1

Robert E. Noonan

68 Compilers and Interpreters 68-1

Kenneth C. Louden and Ronald Mak

69 Programming Language Semantics 69-1

David A. Schmidt

70 Type Systems 70-1

Stephanie Weirich

71 Formal Methods 71-1

Jonathan P. Bowen and Michael G. Hinchey

Part IX Discipline of Software Engineering

72 Discipline of Software Engineering: An Overview 72-1

Jorge L. Díaz-Herrera and Peter A. Freeman

73 Professionalism and Certification 73-1

Stephen B. Seidman

74 Software Engineering Code of Ethics and Professional Practice 74-1

Don Gotterbarn

x Contents

75 Software Business and Economics 75-1

Christof Ebert

76 Open Source and Governance: COTS 76-1

Brian M. Gaff, Gregory J. Ploussios, and Brian R. Landry

Part X Software Quality and Measurement

77 Evidence-Informed Software Engineering and the Systematic Literature

Review 77-1

David Budgen and Pearl Brereton

78 Empirical Software Engineering 78-1

David Budgen and Barbara Kitchenham

79 Software Quality and Model-Based Process Improvement 79-1

Bariş Özkan, Özlem Albayrak, and Onur DemirÖrs

80 Software Metrics and Measurements 80-1

David Zubrow

Part XI Software Development Management: Processes

and Paradigms

81 Software Development: Management and Business Concepts 81-1

Michael A. Cusumano

82 Project Personnel and Organization 82-1

Paul McMahon and Tom McBride

83 Project and Process Control 83-1

James McDonald

84 Agile 84-1

John Favaro

85 Service-Oriented Development 85-1

Andy Wang and Guangzhi Zheng

86 Software Product Lines 86-1

Jorge L. Díaz-Herrera and Melvin Pérez-Cedano

Part XII Software Modeling, Analysis, and Design

87 Requirements Elicitation87-1

Daniel M. Berry

88 Specification 88-1

Andrew McGettrick

89 Software Model Checking 89-1

Alastair Donaldson

Contents xi

90 Software Design Strategies 90-1

Len Bass

91 Software Architecture 91-1

Bedir Tekinerdogan

92 Human–Computer Interfaces for Speech Applications 92-1

Shelby S. Darnell, Naja Mack, France Jackson, Hanan Alnizami, Melva James, Josh

Ekandem, Ignacio Alvarez, Marvin Andujar, Dekita Moon, and Juan E. Gilbert

93 Software Assurance 93-1

Nancy R. Mead, Dan Shoemaker, and Carol Woody

xiii

Preface to the Computing

Handbook Set

The purpose of the Computing Handbook Set is to provide a single, comprehensive reference for spe￾cialists in computer science, information systems, information technology, software engineering, and

other fields who wish to broaden or deepen their understanding in a particular subfield of the comput￾ing discipline. Our goal is to provide up-to-date information on a wide range of topics in a form that is

accessible to students, faculty, and professionals.

The discipline of computing has developed rapidly since CRC Press published the second edition of

the Computer Science Handbook in 2004 (Tucker, 2004). Indeed, it has developed so much that this third

edition requires repartitioning and expanding the topic coverage into a two-volume set.

The need for two volumes recognizes not only the dramatic growth of computing as a discipline but

also the relatively new delineation of computing as a family of five separate disciplines, as described by

their professional societies—The Association for Computing Machinery (ACM), The IEEE Computer

Society (IEEE-CS), and The Association for Information Systems (AIS) (Shackelford et al., 2005).

These separate disciplines are known today as computer engineering, computer science, information

systems, information technology, and software engineering. These names more or less fully encom￾pass the variety of undergraduate and graduate degree programs that have evolved around the world,

with the exception of countries where the term informatics is used for a subset of these disciplines. The

document “Computing curricula 2005: The overview report” describes computing this way (Shackelford

et al., 2005, p. 9):

In a general way, we can define computing to mean any goal-oriented activity requiring, benefit￾ing from, or creating computers. Thus, computing includes designing and building hardware and

software systems for a wide range of purposes; processing, structuring, and managing various

kinds of information; doing scientific studies using computers; making computer systems behave

intelligently; creating and using communications and entertainment media; finding and gathering

information relevant to any particular purpose, and so on.

To add much flesh to the bones of this very broad definition, this handbook set describes in some

depth what goes on in research laboratories, educational institutions, and public and private organiza￾tions to advance the effective development and utilization of computers and computing in today’s world.

The two volumes in this set cover four of the five disciplines in the following way:*

1. Volume I: Computer Science and Software Engineering

2. Volume II: Information Systems and Information Technology

* The fifth discipline, computer engineering, is the subject of a separate handbook published by CRC Press in 2008.