A Textbook of Data Structures and Algorithms, Volume 3
Description
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.
More details
Other editions
Additional editions
Person
G A Vijayalakshmi Pai, SMIEEE, is a Professor of Computer Applications at PSG College of Technology, Coimbatore, India. She has authored books and investigated research projects funded by government agencies in the disciplines of Computational Finance and Computational Intelligence.
Content
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
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
- 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.
- 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,...
