Preface

Efficient problem solving using computers, irrespective of the discipline or application, calls for the design of efficient algorithms. The inclusion of appropriate data structures is of critical importance to the design of efficient algorithms. In other words, good algorithm design must go hand in hand with appropriate data structures for an efficient program design to solve a problem.

Data structures and algorithms is a fundamental course in computer science, which most undergraduate and graduate programs in computer science and other allied disciplines in science and engineering offer during the early stages of the respective programs, either as a core or as an elective course. The course enables students to have a much-needed foundation for efficient programming, leading to better problem solving in their respective disciplines.

Most of the well-known text books/monographs on this subject have discussed the concepts in relation to a programming language - beginning with Pascal and spanning a spectrum of them such as C, C++, C#, Java, Python and so on, essentially calling for ample knowledge of the language, before one proceeds to try and understand the data structure. There does remain a justification in this. The implementation of data structures in the specific programming language need to be demonstrated or the algorithms pertaining to the data structures concerned need a convenient medium of presentation and when this is the case, why not a programming language?

Again, while some authors have insisted on using their books for an advanced level course, there are some who insist on a working knowledge of the specific programming language as a prerequisite to using the book. However, in the case of a core course, as it is in most academic programs, it is not uncommon for a novice or a sophomore to be bewildered by the "miles of code" that demonstrate or explain a data structure, rendering the subject difficult to comprehend. In fact, the efforts that one needs to put in to comprehend the data structure and its applications are distracted by the necessity to garner sufficient programming knowledge to follow the code. It is indeed ironic that while a novice is taught data structures to appreciate programming, in reality it turns out that one learns programming to appreciate data structures!

In my decades-old experience of offering the course to graduate programs, which admits students from diverse undergraduate disciplines, with little to no strong knowledge of programming, I had several occasions to observe this malady. In fact, it is not uncommon in some academic programs, especially graduate programs which, due to their shorter duration, have a course in programming and data structures running in parallel in the same semester, much to the chagrin of the novice learner! That a novice is forced to learn data structures through their implementation (in a specific programming language), when in reality it ought to be learning augmented with the implementation of the data structures, has been the reason behind the fallout.

A solution to this problem would be to

1. Frame the course such that the theory deals with the concepts, techniques and applications of data structures and algorithms, not taking recourse to any specific programming language, but instead settling for a pseudo-language, which clearly expounds the data structure. Additionally, supplementing the course material with illustrative problems, review questions and exercises to reinforce the students' grasp of the concepts would help them gain useful insights while learning.
2. Augment the theory with laboratory sessions to enable the student to implement the data structure in itself or as embedded in an application, in the language of his/her own choice or as insisted upon in the curriculum. This would enable the student who has acquired sufficient knowledge and insight into the data structures to appreciate the beauty and merits of employing the data structure by programming it themself, rather than "look" for the data structure in a prewritten code.

This means that text books catering to the fundamental understanding of the data structure concepts for use as course material in the classroom are as much needed as the books that cater to the implementation of data structures in a programming language for use in the laboratory sessions. While most books in the market conform to the latter, bringing out a book to be classroom course material and used by instructors handling a course on data structures and algorithms, comprehensive enough for the novice students to benefit from, has been the main motivation in writing this book.

As such, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language, discusses several examples and illustrative problems, poses review questions to reinforce the understanding of the theory, and presents a suggestive list of programming assignments to aid implementation of the data structures and algorithms learned.

In fact, the book may either be independently used as a textbook since it is self-contained or serve as a companion for books discussing data structures and algorithms implemented in specific programming languages such as C, C++, Java, Python, and so on.

At this juncture, it needs to be pointed out that a plethora of programming resources and freely downloadable implementations of the majority of the data structures in almost all popular languages are available on the Internet, which can undoubtedly serve as good guides for the learner. However, it has to be emphasized that an earnest student of data structures and algorithms must invest a lot of time and self-effort in trying to implement the data structures and algorithms learned, in a language of one's choice, all by oneself, in order to attain a thorough grasp of the concepts.

About this edition

This edition is a largely revised and enlarged version of its predecessor, published by McGraw Hill, USA. The earlier edition published in 2008 saw 15 reprints in its life span of 13 years (ending January 2022) and was recommended as a text book for the course in several universities and colleges. It comprised 17 chapters categorized into five parts and reinforced learning through 133 illustrative problems, 215 review questions and 74 programming assignments.

The features of this new edition are as follows:

• There are 22 chapters spread across three volumes that detail sequential linear data structures, linked linear data structures, nonlinear data structures, advanced data structures, searching and sorting algorithms, algorithm design techniques and NP-completeness.
• The data structures of k-d trees and treaps have been elaborated in a newly included chapter (Chapter 15) in Volume 3.
• The data structures of strings, bit rays, unrolled linked lists, self-organizing linked lists, segment trees and k-ary trees have been introduced in the appropriate sections of the existing chapters in Volumes 1 and 2.
• The concepts of counting binary search trees and Kruskal's algorithm have been detailed in the appropriate sections of the existing chapters in Volume 2.
• Skip list search, counting sort and bucket sort have been included in the chapters on searching and sorting algorithms in Volume 3.
• The algorithm design techniques of divide and conquer, the greedy method and dynamic programming have been elaborately discussed in Chapters 19-21 in Volume 3.
• The concept of NP-completeness has been detailed in a newly included chapter, Chapter 22 in Volume 3.
• Several illustrative problems, review questions and programming assignments have been added to enrich the content and aid in understanding the concepts. The new edition thus includes 181 illustrative problems, 276 review questions and 108 programming assignments.

Organization of the book

The book comprises three volumes, namely, Volume 1: Chapters 1-7, Volume 2: Chapters 8-12 and Volume 3: Chapters 13-22.

Volume 1 opens with an introduction to data structures and concepts pertaining to the analysis of algorithms, detailed in Chapters 1 and 2, which is essential to appreciate the theories and algorithms related to data structures and their applications.

Chapters 3-5 detail sequential linear data structures, namely, arrays, strings, bit arrays, stacks, queues, priority queues and dequeues, and their applications. Chapters 6 and 7 elucidate linked linear data structures, namely linked lists, linked stacks and linked queues, and their applications.

Volume 2 details nonlinear data structures. Chapters 8 and 9 elaborate on the nonlinear data structures of trees, binary trees and graphs, and their applications. Chapters 10-12 highlight the advanced data structures of binary search trees, AVL trees, B trees, tries, red-black trees and splay trees, and their applications.

Volume 3 details an assortment of data structures, algorithm design strategies and their applications.

Chapters 13-15 discuss hash tables, files, k-d trees and treaps. Chapter 16 discusses the search algorithms of linear search, transpose sequential search, interpolation search, binary search,...