`
`COMPUTER
`Science
`
`h a n d b o o k
`
`EditOR-IN-CHIEF
`Allen B. Tucker
`
`CHAPMAN & HALL/CRC
`
`♦
`
`Published in Cooperation with ACM, The Association for Computing Machinery
`
`© 2004 by Taylor & Francis Group, LLC
`
`0001
`
`Exhibit 1014 page 1 of 65
`DENTAL IMAGING
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`C360X disclaimer.fm Page 1 Thursday, May 20, 2004 3:04 PM
`
`Library of Congress Cataloging-in-Publication Data
`
`Computer science handbook / editor-in-chief, Allen B. Tucker—2nd ed.
`p. cm.
` Includes bibliographical references and index.
` ISBN 1-58488-360-X (alk. paper)
`1.Computer science-Handbooks, manuals, etc. 2. Engineering—Hanbooks, manuals, etc.
`I. Tucker, Allen B.
`
` QA76.C54755 2004
` 004—dc22
`
`2003068758
`
`This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with
`permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish
`reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials
`or for the consequences of their use.
`
`Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical,
`including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior
`permission in writing from the publisher.
`
`All rights reserved. Authorization to photocopy items for internal or personal use, or the personal or internal use of specific
`clients, may be granted by CRC Press LLC, provided that $1.50 per page photocopied is paid directly to Copyright Clearance
`Center, 222 Rosewood Drive, Danvers, MA 01923 USA. The fee code for users of the Transactional Reporting Service is
`ISBN 1-58488-360-X/04/$0.00+$1.50. The fee is subject to change without notice. For organizations that have been
`granted a photocopy license by the CCC, a separate system of payment has been arranged.
`
`The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating new works,
`or for resale. Specific permission must be obtained in writing from CRC Press LLC for such copying.
`
`Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.
`
`Trademark Notice:
`Product or corporate names may be trademarks or registered trademarks, and are used only for
`identification and explanation, without intent to infringe.
`
`Visit the CRC Press Web site at www.crcpress.com
`
`© 2004 by Chapman & Hall/CRC
`
`No claim to original U.S. Government works
`International Standard Book Number 1-58488-360-X
`Library of Congress Card Number 2003068758
`Printed in the United States of America 1 2 3 4 5 6 7 8 9 0
`Printed on acid-free paper
`
`© 2004 by Taylor & Francis Group, LLC
`
`0002
`
`Exhibit 1014 page 2 of 65
`DENTAL IMAGING
`
`
`
`Preface to the Second
`Edition
`
`Purpose
`
`The purpose of The Computer Science Handbook is to provide a single comprehensive reference for com-
`puter scientists, software engineers, and IT professionals who wish to broaden or deepen their understand-
`ing in a particular subfield of computer science. Our goal is to provide the most current information in
`each of the following eleven subfields in a form that is accessible to students, faculty, and professionals in
`computer science:
`
`algorithms, architecture, computational science, graphics, human-computer interaction, infor-
`mation management, intelligent systems, net-centric computing, operating systems, program-
`ming languages, and software engineering
`
`Each of the eleven sections of the Handbook is dedicated to one of these subfields. In addition, the
`appendices provide useful information about professional organizations in computer science, standards,
`and languages. Different points of access to this rich collection of theory and practice are provided through
`the table of contents, two introductory chapters, a comprehensive subject index, and additional indexes.
`A more complete overview of this Handbook can be found in Chapter 1, which summarizes the contents
`of each of the eleven sections. This chapter also provides a history of the evolution of computer science
`during the last 50 years, as well as its current status, and future prospects.
`
`New Features
`
`Since the first edition of the Handbook was published in 1997, enormous changes have taken place in the
`discipline of computer science. The goals of the second edition of the Handbook are to incorporate these
`changes by:
`
`1. Broadening its reach across all 11 subject areas of the discipline, as they are defined in Computing
`Curricula 2001 (the new standard taxonomy)
`2. Including a heavier proportion of applied computing subject matter
`3. Bringing up to date all the topical discussions that appeared in the first edition
`
`This new edition was developed by the editor-in-chief and three editorial advisors, whereas the first
`edition was developed by the editor and ten advisors. Each edition represents the work of over 150
`contributing authors who are recognized as experts in their various subfields of computer science.
`Readers who are familiar with the first edition will notice the addition of many new chapters, reflect-
`ing the rapid emergence of new areas of research and applications since the first edition was published.
`Especially exciting are the addition of new chapters in the areas of computational science, information
`
`© 2004 by Taylor & Francis Group, LLC
`
`0003
`
`Exhibit 1014 page 3 of 65
`DENTAL IMAGING
`
`
`
`management, intelligent systems, net-centric computing, and software engineering. These chapters explore
`topics like cryptography, computational chemistry, computational astrophysics, human-centered software
`development, cognitive modeling, transaction processing, data compression, scripting languages, multi-
`media databases, event-driven programming, and software architecture.
`
`Acknowledgments
`
`A work of this magnitude cannot be completed without the efforts of many individuals. During the 2-year
`process that led to the first edition, I had the pleasure of knowing and working with ten very distinguished,
`talented, and dedicated editorial advisors:
`
`Harold Abelson (MIT), Mikhail Atallah (Purdue), Keith Barker (Uconn), Kim Bruce (Williams),
`John Carroll (VPI), Steve Demurjian (Uconn), Donald House (Texas A&M), Raghu
`Ramakrishnan (Wisconsin), Eugene Spafford (Purdue), Joe Thompson (Mississippi State), and
`Peter Wegner (Brown).
`
`For this edition, a new team of trusted and talented editorial advisors helped to reshape and revitalize
`the Handbook in valuable ways:
`
`Robert Cupper (Allegheny), Fadi Deek (NJIT), Robert Noonan (William and Mary)
`
`All of these persons provided valuable insights into the substantial design, authoring, reviewing, and
`production processes throughout the first eight years of this Handbook’s life, and I appreciate their work
`very much.
`Of course, it is the chapter authors who have shared in these pages their enormous expertise across the
`wide range of subjects in computer science. Their hard work in preparing and updating their chapters is
`evident in the very high quality of the final product. The names of all chapter authors and their current
`professional affiliations are listed in the contributor list.
`I want also to thank Bowdoin College for providing institutional support for this work. Personal thanks
`go especially to Craig McEwen, Sue Theberge, Matthew Jacobson-Carroll, Alice Morrow, and Aaron
`Olmstead at Bowdoin, for their various kinds of support as this project has evolved over the last eight
`years. Bob Stern, Helena Redshaw, Joette Lynch, and Robert Sims at CRC Press also deserve thanks for
`their vision, perseverance and support throughout this period.
`Finally, the greatest thanks is always reserved for my wife Meg – my best friend and my love – for her
`eternal influence on my life and work.
`
`Allen B. Tucker
`Brunswick, Maine
`
`© 2004 by Taylor & Francis Group, LLC
`
`0004
`
`Exhibit 1014 page 4 of 65
`DENTAL IMAGING
`
`
`
`Editor-in-Chief
`
`Allen B. Tucker is the Anne T. and Robert M. Bass Professor of Natural
`Sciences in the Department of Computer Science at Bowdoin College,
`where he has taught since 1988. Prior to that, he held similar positions
`at Colgate and Georgetown Universities. Overall, he has served eighteen
`years as a department chair and two years as an associate dean. At Colgate,
`he held the John D. and Catherine T. MacArthur Chair in Computer
`Science.
`Professor Tucker earned a B.A. in mathematics from Wesleyan Uni-
`versity in 1963 and an M.S. and Ph.D. in computer science from North-
`western University in 1970. He is the author or coauthor of several
`books and articles in the areas of programming languages, natural lan-
`guage processing, and computer science education. He has given many
`talks, panel discussions, and workshop presentations in these areas, and
`has served as a reviewer for various journals, NSF programs, and curriculum projects. He has also served
`as a consultant to colleges, universities, and other institutions in the areas of computer science curriculum,
`software design, programming languages, and natural language processing applications.
`A Fellow of the ACM, Professor Tucker co-authored the 1986 Liberal Arts Model Curriculum in Com-
`puter Science and co-chaired the ACM/IEEE-CS Joint Curriculum Task Force that developed Computing
`Curricula 1991. For these and other related efforts, he received the ACM’s 1991 Outstanding Contribution
`Award, shared the IEEE’s 1991 Meritorious Service Award, and received the ACM SIGCSE’s 2001 Award for
`Outstanding Contributions to Computer Science Education. In Spring 2001, he was a Fulbright Lecturer
`at the Ternopil Academy of National Economy (TANE) in Ukraine. Professor Tucker has been a member
`of the ACM, the NSF CISE Advisory Committee, the IEEE Computer Society, Computer Professionals for
`Social Responsibility, and the Liberal Arts Computer Science (LACS) Consortium.
`
`© 2004 by Taylor & Francis Group, LLC
`
`0005
`
`Exhibit 1014 page 5 of 65
`DENTAL IMAGING
`
`
`
`Contributors
`
`Eric W. Allender
`Rutgers University
`
`Steve Bryson
`NASA Ames Research Center
`
`J.L. Cox
`Brooklyn College, CUNY
`
`James L. Alty
`Loughborough University
`
`Thomas E. Anderson
`University of Washington
`
`M. Pauline Baker
`National Center for
`Supercomputing
`Applications
`
`Steven Bellovin
`AT&T Research Labs
`
`Andrew P. Bernat
`Computer Research
`Association
`
`Douglas C. Burger
`University of Wisconsin
`at Madison
`
`Colleen Bushell
`National Center for
`Supercomputing
`Applications
`
`Derek Buzasi
`U.S. Air Force Academy
`
`William L. Bynum
`College of William and Mary
`
`Bryan M. Cantrill
`Sun Microsystems, Inc.
`
`Brian N. Bershad
`University of Washington
`
`Christopher M. Bishop
`Microsoft Research
`
`Luca Cardelli
`Microsoft Research
`
`David A. Caughy
`Cornell University
`
`Guy E. Blelloch
`Carnegie Mellon University
`
`Vijay Chandru
`Indian Institute of Science
`
`Philippe Bonnet
`University of Copenhagen
`
`Jonathan P. Bowen
`London South Bank University
`
`Kim Bruce
`Williams College
`
`Steve J. Chapin
`Syracuse University
`
`Eric Chown
`Bowdoin College
`
`Jacques Cohen
`Brandeis University
`
`Alan B. Craig
`National Center for
`Supercomputing
`Applications
`
`Maxime Crochemore
`University of Marne-la-Vall´ee
`and King’s College London
`
`Robert D. Cupper
`Allegheny College
`
`Thomas Dean
`Brown Univeristy
`
`Fadi P. Deek
`New Jersey Institute
`of Technology
`
`Gerald DeJong
`University of Illinois at
`Urbana-Champaign
`
`Steven A. Demurjian Sr.
`University of Connecticut
`
`Peter J. Denning
`Naval Postgraduate School
`
`Angel Diaz
`IBM Research
`
`T.W. Doeppner Jr.
`Brown University
`
`© 2004 by Taylor & Francis Group, LLC
`
`0006
`
`Exhibit 1014 page 6 of 65
`DENTAL IMAGING
`
`
`
`Henry Donato
`College of Charleston
`
`Chitra Dorai
`IBM T.J. Watson
`Research Center
`
`Wolfgang Dzida
`Pro Context GmbH
`
`David S. Ebert
`Purdue University
`
`Raimund Ege
`Florida International
`University
`
`Osama Eljabiri
`New Jersey Institute
`of Technology
`
`David Ferbrache
`U.K. Ministry of Defence
`
`Raphael Finkel
`University of Kentucky
`
`John M. Fitzgerald
`Adept Technology
`
`Michael J. Flynn
`Stanford University
`
`Kenneth D. Forbus
`Northwestern University
`
`Stephanie Forrest
`University of New Mexico
`
`Michael J. Franklin
`University of California
`at Berkeley
`
`John D. Gannon
`University of Maryland
`
`Carlo Ghezzi
`Politecnico di Milano
`
`Benjamin Goldberg
`New York University
`
`James R. Goodman
`University of Wisconsin
`at Madison
`
`Jonathan Grudin
`Microsoft Research
`
`Gamil A. Guirgis
`College of Charleston
`
`Jon Hakkila
`College of Charleston
`
`Sandra Harper
`College of Charleston
`
`Frederick J. Heldrich
`College of Charleston
`
`Katherine G. Herbert
`New Jersey Institute
`of Technology
`
`Michael G. Hinchey
`NASA Goddard Space
`Flight Center
`
`Ken Hinckley
`Microsoft Research
`
`Donald H. House
`Texas A&M University
`
`Windsor W. Hsu
`IBM Research
`
`Daniel Huttenlocher
`Cornell University
`
`Yannis E. Ioannidis
`University of Wisconsin
`
`Robert J.K. Jacob
`Tufts University
`
`Sushil Jajodia
`George Mason University
`
`Mehdi Jazayeri
`Technical University of Vienna
`
`Tao Jiang
`University of California
`
`Michael J. Jipping
`Hope College
`
`Deborah G. Johnson
`University of Virginia
`
`Michael I. Jordan
`University of California
`at Berkeley
`
`David R. Kaeli
`Northeastern University
`
`Erich Kalt ´ofen
`North Carolina State University
`
`Subbarao Kambhampati
`Arizona State University
`
`Lakshmi Kantha
`University of Colorado
`
`Gregory M. Kapfhammer
`Allegheny College
`
`Jonathan Katz
`University of Maryland
`
`Arie Kaufman
`State University of New York
`at Stony Brook
`
`Samir Khuller
`University of Maryland
`
`David Kieras
`University of Michigan
`
`David T. Kingsbury
`Gordon and Betty Moore
`Foundation
`
`Danny Kopec
`Brooklyn College, CUNY
`
`Henry F. Korth
`Lehigh University
`
`© 2004 by Taylor & Francis Group, LLC
`
`0007
`
`Exhibit 1014 page 7 of 65
`DENTAL IMAGING
`
`
`
`Kristin D. Krantzman
`College of Charleston
`
`Bruce M. Maggs
`Carnegie Mellon University
`
`Jakob Nielsen
`Nielsen Norman Group
`
`Edward D. Lazowska
`University of Washington
`
`Dino Mandrioli
`Politecnico di Milano
`
`Robert E. Noonan
`College of William and Mary
`
`Thierry Lecroq
`University of Rouen
`
`D.T. Lee
`Northwestern University
`
`Miriam Leeser
`Northeastern University
`
`Henry M. Levy
`University of Washington
`
`M. Lynne Markus
`Bentley College
`
`Tony A. Marsland
`University of Alberta
`
`Edward J. McCluskey
`Stanford University
`
`James A. McHugh
`New Jersey Institute
`of Technology
`
`Frank L. Lewis
`University of Texas at Arlington
`
`Marshall Kirk McKusick
`Consultant
`
`Ming Li
`University of Waterloo
`
`Ying Li
`IBM T.J. Watson
`Research Center
`
`Jianghui Liu
`New Jersey Institute
`of Technology
`
`Kai Liu
`Alcatel Telecom
`
`Clyde R. Metz
`College of Charleston
`
`Keith W. Miller
`University of Illinois
`
`Subhasish Mitra
`Stanford University
`
`Stuart Mort
`U.K. Defence and Evaluation
`Research Agency
`
`Kenneth C. Louden
`San Jose State University
`
`Rajeev Motwani
`Stanford University
`
`Michael C. Loui
`University of Illinois at
`Urbana-Champaign
`
`James J. Lu
`Emory University
`
`Abby Mackness
`Booz Allen Hamilton
`
`Steve Maddock
`University of Sheffield
`
`Klaus Mueller
`State University of New York
`at Stony Brook
`
`Sape J. Mullender
`Lucent Technologies
`
`Brad A. Myers
`Carnegie Mellon University
`
`Peter G. Neumann
`SRI International
`
`Ahmed K. Noor
`Old Dominion University
`
`Vincent Oria
`New Jersey Institute
`of Technology
`
`Jason S. Overby
`College of Charleston
`
`M. Tamer ¨Ozsu
`University of Waterloo
`
`Victor Y. Pan
`Lehman College, CUNY
`
`Judea Pearl
`University of California
`at Los Angeles
`
`Jih-Kwon Peir
`University of Florida
`
`Radia Perlman
`Sun Microsystems Laboratories
`
`Patricia Pia
`University of Connecticut
`
`Steve Piacsek
`Naval Research Laboratory
`
`Roger S. Pressman
`R.S. Pressman & Associates,
`Inc.
`
`J. Ross Quinlan
`University of New South Wales
`
`Balaji Raghavachari
`University of Texas at Dallas
`
`Prabhakar Raghavan
`Verity, Inc.
`
`© 2004 by Taylor & Francis Group, LLC
`
`0008
`
`Exhibit 1014 page 8 of 65
`DENTAL IMAGING
`
`
`
`Z. Rahman
`College of William and Mary
`
`J.S. Shang
`Air Force Research
`
`M.R. Rao
`Indian Institute of
`Management
`
`Bala Ravikumar
`University of Rhode Island
`
`Kenneth W. Regan
`State University of New York
`at Buffalo
`
`Edward M. Reingold
`Illinois Institute of Technology
`
`Alyn P. Rockwood
`Colorado School of Mines
`
`Robert S. Roos
`Allegheny College
`
`Erik Rosenthal
`University of New Haven
`
`Kevin W. Rudd
`Intel, Inc.
`
`Betty Salzberg
`Northeastern University
`
`Pierangela Samarati
`Universit´a degli Studi di
`Milano
`
`Ravi S. Sandhu
`George Mason University
`
`David A. Schmidt
`Kansas State University
`
`Stephen B. Seidman
`New Jersey Institute
`of Technology
`
`Stephanie Seneff
`Massachusetts Institute
`of Technology
`
`Dennis Shasha
`Courant Institute
`New York University
`
`William R. Sherman
`National Center for
`Supercomputing
`Applications
`
`Avi Silberschatz
`Yale University
`
`Gurindar S. Sohi
`University of Wisconsin
`at Madison
`
`Ian Sommerville
`Lancaster University
`
`Bharat K. Soni
`Mississippi State University
`
`William Stallings
`Consultant and Writer
`
`John A. Stankovic
`University of Virginia
`
`S. Sudarshan
`IIT Bombay
`
`Earl E. Swartzlander Jr.
`University of Texas at Austin
`
`Roberto Tamassia
`Brown University
`
`Patricia J. Teller
`University of Texas at ElPaso
`
`Robert J. Thacker
`McMaster University
`
`Nadia Magnenat Thalmann
`University of Geneva
`
`Daniel Thalmann
`Swiss Federal Institute of
`Technology (EPFL)
`
`Alexander Thomasian
`New Jersey Institute of
`Technology
`
`Allen B. Tucker
`Bowdoin College
`
`Jennifer Tucker
`Booz Allen Hamilton
`
`Patrick Valduriez
`INRIA and IRIN
`
`Jason T.L. Wang
`New Jersey Institute
`of Technology
`
`Colin Ware
`University of New Hampshire
`
`Alan Watt
`University of Sheffield
`
`Nigel P. Weatherill
`University of Wales Swansea
`
`Peter Wegner
`Brown University
`
`Jon B. Weissman
`University of Minnesota-Twin
`Cities
`
`Craig E. Wills
`Worcester Polytechnic
`Institute
`
`George Wolberg
`City College of New York
`
`Donghui Zhang
`Northeastern University
`
`Victor Zue
`Massachusetts Institute
`of Technology
`
`© 2004 by Taylor & Francis Group, LLC
`
`0009
`
`Exhibit 1014 page 9 of 65
`DENTAL IMAGING
`
`
`
`Contents
`
`1 Computer Science: The Discipline and its Impact
`Allen B. Tucker and Peter Wegner
`
`2 Ethical Issues for Computer Scientists
`Deborah G. Johnson and Keith W. Miller
`
`Section I: Algorithms and Complexity
`
`3 Basic Techniques for Design and Analysis of Algorithms
`Edward M. Reingold
`
`4 Data Structures
`Roberto Tamassia and Bryan M. Cantrill
`
`5 Complexity Theory
`Eric W. Allender, Michael C. Loui, and Kenneth W. Regan
`
`6 Formal Models and Computability
`Tao Jiang, Ming Li, and Bala Ravikumar
`
`7 Graph and Network Algorithms
`Samir Khuller and Balaji Raghavachari
`
`8 Algebraic Algorithms
`Angel Diaz, Erich Kalt´ofen, and Victor Y. Pan
`
`9 Cryptography
`Jonathan Katz
`
`10 Parallel Algorithms
`Guy E. Blelloch and Bruce M. Maggs
`
`11 Computational Geometry
`D. T. Lee
`
`© 2004 by Taylor & Francis Group, LLC
`
`0010
`
`Exhibit 1014 page 10 of 65
`DENTAL IMAGING
`
`
`
`12 Randomized Algorithms
`Rajeev Motwani and Prabhakar Raghavan
`
`13 Pattern Matching and Text Compression Algorithms
`Maxime Crochemore and Thierry Lecroq
`
`14 Genetic Algorithms
`Stephanie Forrest
`
`15 Combinatorial Optimization
`Vijay Chandru and M. R. Rao
`
`Section II: Architecture and Organization
`16 Digital Logic
`Miriam Leeser
`
`17 Digital Computer Architecture
`David R. Kaeli
`
`18 Memory Systems
`Douglas C. Burger, James R. Goodman, and Gurindar S. Sohi
`
`19 Buses
`Windsor W. Hsu and Jih-Kwon Peir
`
`20 Input/Output Devices and Interaction Techniques
`Ken Hinckley, Robert J. K. Jacob, and Colin Ware
`
`21 Secondary Storage Systems
`Alexander Thomasian
`
`22 High-Speed Computer Arithmetic
`Earl E. Swartzlander Jr.
`
`23 Parallel Architectures
`Michael J. Flynn and Kevin W. Rudd
`
`24 Architecture and Networks
`Robert S. Roos
`
`25 Fault Tolerance
`Edward J. McCluskey and Subhasish Mitra
`
`© 2004 by Taylor & Francis Group, LLC
`
`0011
`
`Exhibit 1014 page 11 of 65
`DENTAL IMAGING
`
`
`
`Section III: Computational Science
`
`26 Geometry-Grid Generation
`Bharat K. Soni and Nigel P. Weatherill
`
`27 Scientific Visualization
`William R. Sherman, Alan B. Craig, M. Pauline Baker, and Colleen Bushell
`
`28 Computational Structural Mechanics
`Ahmed K. Noor
`
`29 Computational Electromagnetics
`J. S. Shang
`
`30 Computational Fluid Dynamics
`David A. Caughey
`
`31 Computational Ocean Modeling
`Lakshmi Kantha and Steve Piacsek
`
`32 Computational Chemistry
`Frederick J. Heldrich, Clyde R. Metz, Henry Donato, Kristin D. Krantzman,
`Sandra Harper, Jason S. Overby, and Gamil A. Guirgis
`
`33 Computational Astrophysics
`Jon Hakkila, Derek Buzasi, and Robert J. Thacker
`
`34 Computational Biology
`David T. Kingsbury
`
`Section IV: Graphics and Visual Computing
`35 Overview of Three-Dimensional Computer Graphics
`Donald H. House
`
`36 Geometric Primitives
`Alyn P. Rockwood
`
`37 Advanced Geometric Modeling
`David S. Ebert
`
`38 Mainstream Rendering Techniques
`Alan Watt and Steve Maddock
`
`39 Sampling, Reconstruction, and Antialiasing
`George Wolberg
`
`© 2004 by Taylor & Francis Group, LLC
`
`0012
`
`Exhibit 1014 page 12 of 65
`DENTAL IMAGING
`
`
`
`40 Computer Animation
`Nadia Magnenat Thalmann and Daniel Thalmann
`
`41 Volume Visualization
`Arie Kaufman and Klaus Mueller
`
`42 Virtual Reality
`Steve Bryson
`
`43 Computer Vision
`Daniel Huttenlocher
`
`Section V: Human-Computer Interaction
`
`44 The Organizational Contexts of Development and Use
`Jonathan Grudin and M. Lynne Markus
`
`45 Usability Engineering
`Jakob Nielsen
`
`46 Task Analysis and the Design of Functionality
`David Kieras
`
`47 Human-Centered System Development
`Jennifer Tucker and Abby Mackness
`
`48 Graphical User Interface Programming
`Brad A. Myers
`
`49 Multimedia
`James L. Alty
`
`50 Computer-Supported Collaborative Work
`Fadi P. Deek and James A. McHugh
`
`51 Applying International Usability Standards
`Wolfgang Dzida
`
`Section VI:
`
`Information Management
`
`52 Data Models
`Avi Silberschatz, Henry F. Korth, and S. Sudarshan
`
`53 Tuning Database Design for High Performance
`Dennis Shasha and Philippe Bonnet
`
`© 2004 by Taylor & Francis Group, LLC
`
`0013
`
`Exhibit 1014 page 13 of 65
`DENTAL IMAGING
`
`
`
`54 Access Methods
`Betty Salzberg and Donghui Zhang
`
`55 Query Optimization
`Yannis E. Ioannidis
`
`56 Concurrency Control and Recovery
`Michael J. Franklin
`
`57 Transaction Processing
`Alexander Thomasian
`
`58 Distributed and Parallel Database Systems
`M. Tamer ¨Ozsu and Patrick Valduriez
`
`59 Multimedia Databases: Analysis, Modeling, Querying, and Indexing
`Vincent Oria, Ying Li, and Chitra Dorai
`
`60 Database Security and Privacy
`Sushil Jajodia
`
`Section VII:
`
`Intelligent Systems
`
`61 Logic-Based Reasoning for Intelligent Systems
`James J. Lu and Erik Rosenthal
`
`62 Qualitative Reasoning
`Kenneth D. Forbus
`
`63 Search
`D. Kopec, T.A. Marsland, and J.L. Cox
`
`64 Understanding Spoken Language
`Stephanie Seneff and Victor Zue
`
`65 Decision Trees and Instance-Based Classifiers
`J. Ross Quinlan
`
`66 Neural Networks
`Michael I. Jordan and Christopher M. Bishop
`
`67 Planning and Scheduling
`Thomas Dean and Subbarao Kambhampati
`
`68 Explanation-Based Learning
`Gerald DeJong
`
`69 Cognitive Modeling
`Eric Chown
`
`© 2004 by Taylor & Francis Group, LLC
`
`0014
`
`Exhibit 1014 page 14 of 65
`DENTAL IMAGING
`
`
`
`70 Graphical Models for Probabilistic and Causal Reasoning
`Judea Pearl
`
`71 Robotics
`Frank L. Lewis, John M. Fitzgerald, and Kai Liu
`
`Section VIII: Net-Centric Computing
`
`72 Network Organization and Topologies
`William Stallings
`
`73 Routing Protocols
`Radia Perlman
`
`74 Network and Internet Security
`Steven Bellovin
`
`75 Information Retrieval and Data Mining
`Katherine G. Herbert, Jason T.L. Wang, and Jianghui Liu
`
`76 Data Compression
`Z. Rahman
`
`77 Security and Privacy
`Peter G. Neumann
`
`78 Malicious Software and Hacking
`David Ferbrache and Stuart Mort
`
`79 Authentication, Access Control, and Intrusion Detection
`Ravi S. Sandhu and Pierangela Samarati
`
`Section IX: Operating Systems
`
`80 What Is an Operating System?
`Raphael Finkel
`
`81 Thread Management for Shared-Memory Multiprocessors
`Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska,
`and Henry M. Levy
`
`82 Process and Device Scheduling
`Robert D. Cupper
`
`83 Real-Time and Embedded Systems
`John A. Stankovic
`
`© 2004 by Taylor & Francis Group, LLC
`
`0015
`
`Exhibit 1014 page 15 of 65
`DENTAL IMAGING
`
`
`
`84 Process Synchronization and Interprocess Communication
`Craig E. Wills
`
`85 Virtual Memory
`Peter J. Denning
`
`86 Secondary Storage and Filesystems
`Marshall Kirk McKusick
`
`87 Overview of Distributed Operating Systems
`Sape J. Mullender
`
`88 Distributed and Multiprocessor Scheduling
`Steve J. Chapin and Jon B. Weissman
`
`89 Distributed File Systems and Distributed Memory
`T. W. Doeppner Jr.
`
`Section X: Programming Languages
`
`90 Imperative Language Paradigm
`Michael J. Jipping and Kim Bruce
`
`91 The Object-Oriented Language Paradigm
`Raimund Ege
`
`92 Functional Programming Languages
`Benjamin Goldberg
`
`93 Logic Programming and Constraint Logic Programming
`Jacques Cohen
`
`94 Scripting Languages
`Robert E. Noonan and William L. Bynum
`
`95 Event-Driven Programming
`Allen B. Tucker and Robert E. Noonan
`
`96 Concurrent/Distributed Computing Paradigm
`Andrew P. Bernat and Patricia Teller
`
`97 Type Systems
`Luca Cardelli
`
`98 Programming Language Semantics
`David A. Schmidt
`
`© 2004 by Taylor & Francis Group, LLC
`
`0016
`
`Exhibit 1014 page 16 of 65
`DENTAL IMAGING
`
`
`
`99 Compilers and Interpreters
`Kenneth C. Louden
`
`100 Runtime Environments and Memory Management
`Robert E. Noonan and William L. Bynum
`
`Section XI: Software Engineering
`
`101 Software Qualities and Principles
`Carlo Ghezzi, Mehdi Jazayeri, and Dino Mandrioli
`
`102 Software Process Models
`Ian Sommerville
`
`103 Traditional Software Design
`Steven A. Demurjian Sr.
`
`104 Object-Oriented Software Design
`Steven A. Demurjian Sr. and Patricia J. Pia
`
`105 Software Testing
`Gregory M. Kapfhammer
`
`106 Formal Methods
`Jonathan P. Bowen and Michael G. Hinchey
`
`107 Verification and Validation
`John D. Gannon
`
`108 Development Strategies and Project Management
`Roger S. Pressman
`
`109 Software Architecture
`Stephen B. Seidman
`
`110 Specialized System Development
`Osama Eljabiri and Fadi P. Deek
`
`Appendix A: Professional Societies in Computing
`
`Appendix B: The ACM Code of Ethics and Professional Conduct
`
`Appendix C: Standards-Making Bodies and Standards
`
`Appendix D: Common Languages and Conventions
`
`© 2004 by Taylor & Francis Group, LLC
`
`0017
`
`Exhibit 1014 page 17 of 65
`DENTAL IMAGING
`
`
`
`48
`
`Graphical User
`Interface
`Programming
`
`48.1
`48.2
`
`Introduction
`Importance of User Interface Tools
`Overview of User Interface Software Tools
`• Tools for the World Wide Web
`48.3 Models of User Interface Software
`48.4 Technology Transfer
`48.5 Research Issues
`New Programming Languages • Increased Depth
`• Increased Breadth • End User Programming
`and Customization • Application and User Interface
`Separation • Tools for the Tools
`48.6 Conclusions
`
`Brad A. Myers
`Carnegie Mellon University
`
`48.1 Introduction∗
`
`Almost as long as there have been user interfaces, there have been special software systems and tools to
`help design and implement the user interface software. Many of these tools have demonstrated significant
`productivity gains for programmers and have become important commercial products. Others have proved
`less successful at supporting the kinds of user interfaces people want to build. Virtually all applications
`today are built using some form of user interface tool [Myers 2000].
`User interface (UI) software is often large, complex, and difficult to implement, debug, and modify. As
`interfaces become easier to use, they become harder to create [Myers 1994]. Today, direct-manipulation
`interfaces (also called GUIs for graphical user interfaces) are almost universal. These interfaces require
`that the programmer deal with elaborate graphics, multiple ways of giving the same command, multiple
`asynchronous input devices (usually a keyboard and a pointing device such as a mouse), a mode-free in-
`terface where the user can give any command at virtually any time, and rapid “semantic feedback” where
`determining the appropriate response to user actions requires specialized information about the objects
`in the program. Interfaces on handheld devices, such as a Palm organizer or a Microsoft PocketPC device,
`use similar metaphors and implementation strategies. Tomorrow’s user interfaces will provide speech
`
`∗
`
`This chapter is revised from an earlier version: Brad A. Myers. 1995. “User Interface Software Tools,” ACM Trans-
`actions on Computer–Human Interaction. 2(1): 64–103.
`
`© 2004 by Taylor & Francis Group, LLC
`
`0018
`
`Exhibit 1014 page 18 of 65
`DENTAL IMAGING
`
`
`
`recognition, vision from cameras, 3-D, intelligent agents, and integrated multimedia, and will probably
`be even more difficult to create. Furthermore, because user interface design is so difficult, the only reliable
`way to get good interfaces is to iteratively redesign (and therefore reimplement) the interfaces after user
`testing, which makes the implementation task even harder.
`Fortunately, there has been significant progress in software tools to help with creating user interfaces.
`Today, virtually all user interface software is created using tools that make the implementation easier.
`For example, the MacApp system from Apple, one of the first GUI frameworks, was reported to reduce
`development time by a factor of four or five [Wilson 1990]. A study commissioned by NeXT claimed that
`the average application programmed using the NeXTStep environment wrote 83% fewer lines of code and
`took one-half the time, compared to applications written using less advanced tools, and some applications
`were completed in one-tenth the time. Over three million programmers use Microsoft’s Visual Basic tool
`because it allows them to create GUIs for Windows significantly more quickly.
`This chapter surveys UI software tools and explains the different types and classifications. However, it is
`now impossible to discuss all UI tools, because there are so many, and new research tools are reported every
`year at conferences such as the annual ACM User Interface Software and Technology Symposium (UIST)
`(see http://www.acm.org/uist/) and the ACM SIGCHI conference (see http://www.acm.org/sigchi/). There
`are also about three Ph.D. theses on UI tools every year. This article provides an overview of the most
`popular approaches, rather than an exhaustive survey. It has been updated from previous versions (e.g.,
`[Myers 1995]).
`
`48.2 Importance of User Interface Tools
`
`There are many advantages to using user interface software tools. These can be classified into two main
`groups. First, the quality of the resulting user interfaces might be higher, for the following reasons:
`
`Designs can be rapidly prototyped and implemented, possibly even before the application code is
`written. This, in turn, enables more rapid prototyping and therefore more iterations of iterative
`design, which is a crucial component of achieving high-quality user interfaces [Nielsen 1993b].
`The reliability of the user interface will be higher, because the code for the user interface is created
`automatically from a higher-level specification.
`Different applications are more likely to have consistent user interfaces if they are created using the same
`UI tool.
`It will be easier for a variety of specialists to be involved in designing the user interface, rather than
`having the user interface created entirely by programmers. Graphic artists, cognitive psychologists,
`and usability specialists may all be involved. In particular, professional user interface designers,
`who may not be programmers, can be in charge of the overall design.
`More effort can be expended on the tool than may be practical on any single user interface, because the
`tool will be used with many different applications.
`Undo, Help, and other features are more likely to be available because the tools might support them.
`
`Second, the UI code might be easier and more economical to create and maintain. This is because of the
`following:
`
`Interface specifications can be represented, validated, and evaluated more easily.
`There will be less code to write, because much is supplied by the tools.
`There will be better modularization, due to the separation of the UI component from the application.
`This should allow the user interface to change without affecting the application, and a large class of
`changes to the application (such as changing the internal algorithms) should be possible without
`affecting the user interface.
`The level of programming expertise of the interface designers and implementers can be lower, because
`the tools hide much of the complexity of the underlying system.
`It will be easier to port an application to different hardware and software environments because the
`device dependencies are isolated in the UI tool.
`
`© 2004 by Taylor & Francis Group, LLC
`
`0019
`
`Exhibit 1014 page 19 of 65
`DENTAL IMAGING
`
`
`
`Application
`
`Higher Level Tools
`
`Toolkit
`Windowing System
`
`Operating System
`
`FIGURE 48.1 The components of user interface software.
`
`48.2.1 Overview of User Interf