Contents Preface vii 1 Analyzing Algorithms and Problems: Principles and Examples 1 1.1 Introduction 2 1.2 Java as an Algorithm Language 3 1.3 Mathematical Background 11 1.4 Analyzing Algorithms and Problems 30 1.5 Classifying Functions by Their Asymptotic Growth Rates 43 1.6 Searching an Ordered Array 53 Exercises 61 Notes and References 67 2 Data Abstraction and Basic Data Structures 69 2.1 Introduction 70 2.2 ADT Specification and Design Techniques 71 2.3 Elementary ADTs-Lists and Trees 73 2.4 Stacks and Queues 86 2.5 ADTs for Dynamic Sets 89 Exercises 95 Notes and References 100 3 Recursion and Induction 101 3.1 Introduction 102 3.2 Recursive Procedures 102 3.3 What Is a Proof？108 3.4 Induction Proofs 111 3.5 Proving Correctness of Procedures 118