25 D 23 D Abstract 23 Data Types and Algorithms Second Edition Manoochehr Azmoodeh 23.5 A 24 E 2
Contents Preface Acknowledgements xiv Preliminaries and Notation PART I:Design and Analysis of Data Types 1 1 The Complexity of Algorithms 2 1.1 Comparing the Efficiency of Algorithms 2 1.2 Time and Space Complexity of Algorithms 6 1.3 Asymptotic Time Complexity-Big O and Big S Notations 9 1.4 Importance of Growth Rate of Time Complexities 12 1.5 Rules for Deriving Time Complexities of Pascal Programs 14 Exercises 21 Bibliographic Notes and Further Reading 23 2 Abstract Data Types and Program Design 25 2.1 Elements of Program Design 25 2.2 Abstraction Mechanisms in Program Design Process 27 2.3 Formal Specification of Abstract Data Types 39 Exercises 43 Bibliographic Notes and Further Reading 44 3 Elementary (Linear)ADTs 48 3.1 The ADT Stack 48 3.2 The ADT Queue 58 3.3 The ADT List 64 3.4 Case Study:Evaluation of Arithmetic Expressions 9 Exercises 86 Bibliographic Notes and Further Reading 89 4 Non-linear ADTs-Trees 91 4.1 Trees 4.2 Binary Trees 4.3 Threaded Binary Trees 9910 4.4 Binary Search Trees 5
vili Contents 4.5 Balanced Trees:AVL Trees 112 4.6 Balanced Trees:B-trees 122 Exercises 131 Bibliographic Notes and Further Reading 134 5 Abstract Data Type Sets-I 136 5.1 ADT Set:Definitions 137 5.2 Implementing Sets using Bit-vectors 139 5.3 Implementing Sets using Lists 141 5.4 Implementing Sets using Trees 145 Exercises 149 Bibliographic Notes and Further Reading 150 6 Abstract Data Type Sets-II 152 6.1 ADT Mapping 152 6.2 Hashing (Key Transformation) 155 6.3 Priority Queues 170 6.4 The ADT Relation 178 Exercises 189 Bibliographic Notes and Further Reading 197 7 Non-Linear ADTs-Graphs 200 7.1 Definitions and Terminology 200 7.2 ADT Graph and its Implementation 203 7.3 Spanning Trees 206 7.4 Path-finding Algorithms 217 Exercises 224 Bibliographic Notes and Further Reading 228 PART II:Algorithm Design with Abstract Data Types 231 8 Techniques for Developing Efficient Algorithms 232 8.1 Divide and Conquer 232 8.2 Dynamic Programming 237 8.3 Other Techniques 245 Exercises 245 Bibliographic Notes and Further Reading 249 9 Sorting:an Algorithm on the ADT List 251 9.1 An Abstract Sorting Algorithm 251 9.2 Easy Split/Hard Join Sorting Algorithms 254 9.3 Hard Split/Easy Join Sorting Algorithms 259 9.4 Sorting by Utilising the Representation of Elements 270 9.5 Taxonomy,Comparisons and Related Issues 273
Contents iⅸ Exercises 277 Bibliographic Notes and Further Reading 279 10 Graph Traversals and Algorithms 281 10.1 Depth First Search 281 10.2 Breadth First Search 283 10.3 Detection of Cycles 285 10.4 Topological Ordering 287 10.5 Connectedness of Graphs 290 Exercises 292 Bibliographic Notes and Further Reading 293 11 String-searching Algorithms 295 11.1 Definitions 295 11.2 Data Structures for Strings 296 11.3 String-searching Algorithms 297 11.4 String-searching in Large Static Strings 307 Exercises 310 Bibliographic Notes and Further Reading 311 12 Hard'Problems and NP-completeness 313 12.1 NP-problems and NP-complete Problems 315 12.2 Methods for Solving 'Hard'Problems 318 Exercises 329 Bibliographic Notes and Further Reading 332 Solutions to Selected Exercises 335 Index 373
Preface This book is intended as a second course on programming with data structures. The concepts of 'data structures'and their impact on design and efficiency of computer algorithms are well established and well studied.For instance,see the authoritative text by D.E.Knuth,The Art of Computer Programming (Knuth, 1973),and The Design and Analysis of Computer Algorithms by A.V.Aho, J.E.Hopcroft and J.O.Ullman (Aho et al.,1974).Because of their long stand- ing history,'data structures'and their role in program design are well understood, and in the last decade or so,numerous textbooks have appeared in this field.For instance,see Baron and Shapiro (1980),Aho et al.(1974),Gotlieb and Gotlieb (1978),Stubbs and Webre (1985),Reingold and Hansen (1983),Korsh (1986), Wirth (1976)and Martin (1986). However,following general design methods based on high-level abstraction of systems (computer systems,engineering systems,etc.)and their modular decom- positions,'data structures'have also been studied in this modular framework. The approach taken is based on the notion of an Abstract Data Type which is defined as an abstract mathematical model with a defined set of operations.The treatment of abstract data types is very informal.The specification of data types and their corresponding operations are presented in a form directly representable in a Pascal-like language. The textbook Data Structures and Algorithms by A.V.Aho,J.E.Hopcroft and J.D.Ullman (Aho et al.,1983)is a pioneering work incorporating the notion of abstraction in the design of data structures.Other texts following a similar approach have appeared:Stubbs and Webre (1985),Wirth (1986)and Martin (1986).This book follows the same general principles as the above,in particular, Aho et.al.(1983)in describing data abstractions in languages such as Pascal. However,the material and programs are more structured and relationships between ADTs and implementations are made more clear. The primary advantage gained by using abstract data types in program design is that they lead to better structured and modular programs.This type of modu- larity ensures that logical tasks and data are grouped together to form an inde- pendent module whose functional specification is visible to other programs using it.These application programs do not require detailed information on how the tasks and data are realised in computer hardware.Thus various strategies may be used to implement a module's data types and operations so far as they conform to the specification of that module.This separation of specification and imple- mentation of programs ensure that many design decisions,such as efficiency, trade-offs between speed and storage etc.,can be made at a later stage when the