Computer Science 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 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 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 v 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 Systems34-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