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