Data structures and algorithms is a fundamental course in Computer Science, which enables learners across any discipline to develop the much-needed foundation of efficient programming, leading to better problem solving in their respective disciplines. A Textbook of Data Structures and Algorithms is a textbook that can be used as course material in classrooms, or as self-learning material. The book targets novice learners aspiring to acquire advanced knowledge of the topic. Therefore, the content of the book has been pragmatically structured across three volumes and kept comprehensive enough to help them in their progression from novice to expert. With this in mind, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language. It includes 181 illustrative problems and 276 review questions to reinforce a theoretical understanding and presents a suggestive list of 108 programming assignments to aid in the implementation of the methods covered.

Table of Contents:
Preface xi Acknowledgments xvii Chapter 13 Hash Tables 1 13.1 Introduction 1 13.1.1 Dictionaries 1 13.2 Hash table structure 2 13.3 Hash functions 4 13.3.1 Building hash functions 4 13.4 Linear open addressing 5 13.4.1 Operations on linear open addressed hash tables 8 13.4.2 Performance analysis 10 13.4.3 Other collision resolution techniques with open addressing 11 13.5 Chaining 13 13.5.1 Operations on chained hash tables 15 13.5.2 Performance analysis 17 13.6 Applications 18 13.6.1 Representation of a keyword table in a compiler 18 13.6.2 Hash tables in the evaluation of a join operation on relational databases 19 13.6.3 Hash tables in a direct file organization 22 13.7 Illustrative problems 23 Chapter 14 File Organizations 33 14.1 Introduction 33 14.2 Files 34 14.3 Keys 36 14.4 Basic file operations 38 14.5 Heap or pile organization 38 14.5.1 Insert, delete and update operations 39 14.6 Sequential file organization 39 14.6.1 Insert, delete and update operations 39 14.6.2 Making use of overflow blocks 40 14.7 Indexed sequential file organization 41 14.7.1 Structure of the ISAM files 41 14.7.2 Insert, delete and update operations for a naïve ISAM file 42 14.7.3 Types of indexing 43 14.8 Direct file organization 48 14.9 Illustrative problems 50 Chapter 15 k-d Trees and Treaps 61 15.1 Introduction 61 15.2 k-d trees: structure and operations 61 15.2.1 Construction of a k-d tree 65 15.2.2 Insert operation on k-d trees 69 15.2.3 Find minimum operation on k-d trees 70 15.2.4 Delete operation on k-d trees 72 15.2.5 Complexity analysis and applications of k-d trees 74 15.3 Treaps: structure and operations 76 15.3.1 Treap structure 76 15.3.2 Operations on treaps 77 15.3.3 Complexity analysis and applications of treaps 82 15.4 Illustrative problems 83 Chapter 16 Searching 93 16.1 Introduction 93 16.2 Linear search 94 16.2.1 Ordered linear search 94 16.2.2 Unordered linear search 94 16.3 Transpose sequential search 96 16.4 Interpolation search 98 16.5 Binary search 100 16.5.1 Decision tree for binary search 101 16.6 Fibonacci search 104 16.6.1 Decision tree for Fibonacci search 105 16.7 Skip list search 108 16.7.1 Implementing skip lists 112 16.7.2 Insert operation in a skip list 113 16.7.3 Delete operation in a skip list 114 16.8 Other search techniques 116 16.8.1 Tree search 116 16.8.2 Graph search 116 16.8.3 Indexed sequential search 116 16.9 Illustrative problems 118 Chapter 17 Internal Sorting 131 17.1 Introduction 131 17.2 Bubble sort 132 17.2.1 Stability and performance analysis 134 17.3 Insertion sort 135 17.3.1 Stability and performance analysis 136 17.4 Selection sort 138 17.4.1 Stability and performance analysis 140 17.5 Merge sort 140 17.5.1 Two-way merging 141 17.5.2 k-way merging 143 17.5.3 Non-recursive merge sort procedure 144 17.5.4 Recursive merge sort procedure 145 17.6 Shell sort 147 17.6.1 Analysis of shell sort 153 17.7 Quick sort 153 17.7.1 Partitioning 153 17.7.2 Quick sort procedure 156 17.7.3 Stability and performance analysis 158 17.8 Heap sort 159 17.8.1 Heap 159 17.8.2 Construction of heap 160 17.8.3 Heap sort procedure 163 17.8.4 Stability and performance analysis 167 17.9 Radix sort 167 17.9.1 Radix sort method 167 17.9.2 Most significant digit first sort 171 17.9.3 Performance analysis 171 17.10 Counting sort 171 17.10.1 Performance analysis 175 17.11 Bucket sort 175 17.11.1 Performance analysis 178 17.12 Illustrative problems 179 Chapter 18 External Sorting 197 18.1 Introduction 197 18.1.1 The principle behind external sorting 197 18.2 External storage devices 198 18.2.1 Magnetic tapes 199 18.2.2 Magnetic disks 200 18.3 Sorting with tapes: balanced merge 202 18.3.1 Buffer handling 204 18.3.2 Balanced P-way merging on tapes 205 18.4 Sorting with disks: balanced merge 206 18.4.1 Balanced k-way merging on disks 207 18.4.2 Selection tree 208 18.5 Polyphase merge sort 212 18.6 Cascade merge sort 214 18.7 Illustrative problems 216 Chapter 19 Divide and Conquer 229 19.1 Introduction 229 19.2 Principle and abstraction 229 19.3 Finding maximum and minimum 231 19.3.1 Time complexity analysis 232 19.4 Merge sort 233 19.4.1 Time complexity analysis 233 19.5 Matrix multiplication 234 19.5.1 Divide and Conquer-based approach to “high school” method of matrix multiplication 234 19.5.2 Strassen’s matrix multiplication algorithm 236 19.6 Illustrative problems 239 Chapter 20 Greedy Method 245 20.1 Introduction 245 20.2 Abstraction 245 20.3 Knapsack problem 246 20.3.1 Greedy solution to the knapsack problem 247 20.4 Minimum cost spanning tree algorithms 249 20.4.1 Prim’s algorithm as a greedy method 250 20.4.2 Kruskal’s algorithm as a greedy method 250 20.5 Dijkstra’s algorithm 251 20.6 Illustrative problems 251 Chapter 21 Dynamic Programming 261 21.1 Introduction 261 21.2 0/1 knapsack problem 263 21.2.1 Dynamic programming-based solution 264 21.3 Traveling salesperson problem 266 21.3.1 Dynamic programming-based solution 267 21.3.2 Time complexity analysis and applications of traveling salesperson problem 269 21.4 All-pairs shortest path problem 269 21.4.1 Dynamic programming-based solution 270 21.4.2 Time complexity analysis 272 21.5 Optimal binary search trees 272 21.5.1 Dynamic programming-based solution 274 21.5.2 Construction of the optimal binary search tree 276 21.5.3 Time complexity analysis 279 21.6 Illustrative problems 280 Chapter 22 P and NP Class of Problems 287 22.1 Introduction 287 22.2 Deterministic and nondeterministic algorithms 289 22.3 Satisfiability problem 292 22.3.1 Conjunctive normal form and Disjunctive normal form 294 22.3.2 Definition of the satisfiability problem 294 22.3.3 Construction of CNF and DNF from a logical formula 295 22.3.4 Transformation of a CNF into a 3-CNF 296 22.3.5 Deterministic algorithm for the satisfiability problem 297 22.3.6 Nondeterministic algorithm for the satisfiability problem 297 22.4 NP-complete and NP-hard problems 297 22.4.1 Definitions 298 22.5 Examples of NP-hard and NP-complete problems 300 22.6 Cook’s theorem 302 22.7 The unsolved problem P = NP 303 22.8 Illustrative problems 304 References 311 Index 313 Summaries of other volumes 317