Preface I Foundation Introduction 1 The Role of Algorithms in Computing 1.1 Algorithms 1.2 Algorithms as a technology 2 Getting Started 2.1 Insertion sort 2.2 Analyzing algorithms 2.3 Designing algorithms 3 Growth of Functions 3.1 Asymptotic notation 3.2 Standard notations and common functions 4 Recurrences 4.1 The substitution method 4.2 The recursion-tree method 4.3 The master method 4.4 Proof of the master theorem 5 Probabilistic Analysis and Randomized Algorithms 5.1 The hiring problem 5.2 Indicator random variables 5.3 Randomized algorithms 5.4 Probabi1istic analysis and further uses of indicator II Sorting and Order Statistics Introduction 6 Heapsort 6.1 Heaps 6.2 Maintaining the heap property 6.3 Building a heap 6.4 The heapsort algorithm 6.5 Priority queues 7 Quicksort 7.1 Description of quicksort 7.2 Performance ofquicksort 7.3 A randomized version of quicksort 7.4 Analysis ofquicksort 8 Sorting in Linear Time 8.1 Lower bounds for sorting 8.2 Counting sort 8.3 Radix sort 8.4 Bucket sort 9 Medians and Order Statistics 9.1 Minimum and maximum 9.2 Selection in expected linear time 9.3 Selection in worst-case linear time III Data Structures Introduction 10 Elementary Data Structures 10.1 Stacks and queues 10.2 Linked lists 10.3 Implementing pointers and objects 10.4 Representing rooted trees 11 Hash Tables 11.1 Direct-address tables 11.2 Hash tables 11.3 Hash functions 11.4 Open addressing 11.5 Perfect hashing 12 Binary Search Trees 12.1 What is a binary search tree? 12.2 Querying a binary search tree 12.3 Insertion and deletion 12.4 Randoinly built binary search trees 13 Red-Black Thees 13.1 Properties of red-black trees 13.2 Rotations 13.3 Insertion 13.4 Deletion 14 Augmenting Data Structures 14.1 Dynamic order statistics 14.2 How to augment a data structure 14.3 Interval trees IV Advanced Desthe and Analysis Techniques …… V Advanced Data Structures VI Graph Algorithms VII Selected Topics VIII Appendix: Mathematical Background Bibliography Index