Contents

Advance Praise v
More from the Reviewers vi
Preface ix
1. Introduction 1
1.1 History of Algorithms 2
1.2 Definition, Structure and Properties of Algorithms 3
1.3 Development of an Algorithm 4
1.4 Data Structures and Algorithms 4
1.5 Data Structure—Definition and Classification 5
Summary 7
2. Analysis of Algorithms 8
2.1 Efficiency of Algorithms 8
2.2 Apriori Analysis 9
2.3 Asymptotic Notations 11
2.4 Time Complexity of an Algorithm Using O Notation 12
2.5 Polynomial Vs Exponential Algorithms 12
2.6 Average, Best and Worst Case Complexities 13
2.7 Analyzing Recursive Programs 15
Summary 19
Illustrative Problems 20
Review Questions 25
Part I
3. Arrays 26
3.1 Introduction 26
3.2 Array Operations 27
3.3 Number of Elements in an Array 27
3.4 Representation of Arrays in Memory 28
3.5 Applications 32
Summary 34
Illustrative Problems 35
Review Questions 37
Programming Assignments 37
xvi Contents

4. Stacks 39
4.1 Introduction 39
4.2 Stack Operations 40
4.3 Applications 43
Summary 48
Illustrative Problems 49
Review Questions 54
Programming Assignments 55
5. Queues 56
5.1 Introduction 56
5.2 Operations on Queues 57
5.3 Circular Queues 62
5.4 Other Types of Queues 66
5.5 Applications 71
Summary 75
Illustrative Problems 76
Review Questions 81
Programming Assignments 82
Part II
6. Linked Lists 84
6.1 Introduction 84
6.2 Singly Linked Lists 87
6.3 Circularly Linked Lists 93
6.4 Doubly Linked Lists 98
6.5 Multiply Linked Lists 103
6.6 Applications 105
Summary 112
Illustrative Problems 113
Review Questions 119
Programming Assignments 121
7. Linked Stacks and Linked Queues 123
7.1 Introduction 123
7.2 Operations on Linked Stacks and Linked Queues 124
7.3 Dynamic Memory Management and Linked Stacks 130
7.4 Implementation of Linked Representations 132
7.5 Applications 133
Summary 137
Illustrative Problems 137
Review Questions 148
Programming Assignments 149
Part III
8. Trees and Binary Trees 151
8.1 Introduction 151
Contents xvii

8.2 Trees: Definition and Basic Terminologies 151

8.3 Representation of Trees 153
8.4 Binary Trees: Basic Terminologies and Types 155
8.5 Representation of Binary Trees 156
8.6 Binary Tree Traversals 158
8.7 Threaded Binary Trees 167
8.8 Application 169
Summary 175
Illustrative Problems 175
Review Questions 184
Programming Assignments 185
9. Graphs 186
9.1 Introduction 186
9.2 Definitions and Basic Terminologies 187
9.3 Representations of Graphs 195
9.4 Graph Traversals 199
9.5 Applications 203
Summary 209
Illustrative Problems 209
Review Questions 214
Programming Assignments 216
Part IV
10. Binary Search Trees and AVL Trees 218
10.1 Introduction 218
10.2 Binary Search Trees: Definition and Operations 218
10.3 AVL Trees: Definition and Operations 228
10.4 Applications 243
Summary 246
Illustrative Problems 247
Review Questions 259
Programming Assignments 260
11. B Trees and Tries 262
11.1 Introduction 262
11.2 m-way search trees: Definition and Operations 262
11.3 B Trees: Definition and Operations 269
11.4 Tries: Definition and Operations 277
11.5 Applications 281
Summary 284
Illustrative Problems 285
Review Questions 290
Programming Assignments 292
12. Red-Black Trees and Splay Trees 293
12.1 Red-Black Trees 293
12.2 Splay Trees 311
xviii Contents

12.3 Applications 318

Summary 319
Illustrative Problems 319
Review Questions 329
Programming Assignments 330
13. Hash Tables 331
13.1 Introduction 331
13.2 Hash Table Structure 332
13.3 Hash Functions 333
13.4 Linear Open Addressing 334
13.5 Chaining 339
13.6 Applications 342
Summary 346
Illustrative Problems 347
Review Questions 351
Programming Assignments 352
14. File Organizations 353
14.1 Introduction 353
14.2 Files 354
14.3 Keys 355
14.4 Basic File Operations 356
14.5 Heap or Pile Organization 356
14.6 Sequential File Organisation 357
14.7 Indexed Sequential File Organization 358
14.8 Direct File Organization 363
Illustrative Problems 365
Summary 369
Review Questions 370
Programming Assignments 371
Part V
15. Searching 373
15.1 Introduction 373
15.2 Linear Search 373
15.3 Transpose Sequential Search 375
15.4 Interpolation Search 376
15.5 Binary Search 378
15.6 Fibonacci Search 381
15.7 Other Search Techniques 384
Summary 385
Illustrative Problems 386
Review Questions 391
Programming Assignments 393
16. Internal Sorting 394
16.1 Introduction 394
Contents xix

16.2 Bubble Sort 395

16.3 Insertion Sort 396
16.4 Selection Sort 399
16.5 Merge Sort 401
16.6 Shell Sort 405
16.7 Quick Sort 410
16.8 Heap Sort 414
16.9 Radix Sort 422
Summary 426
Illustrative Problems 426
Review Questions 433
Programming Assignments 434
17. External Sorting 435
17.1 Introduction 435
17.2 External Storage Devices 436
17.3 Sorting with Tapes: Balanced Merge 438
17.4 Sorting with Disks: Balanced Merge 441
17.5 Polyphase Merge Sort 445
17.6 Cascade Merge Sort 447
Summary 449
Illustrative Problems 449
Review Questions 455
Programming Assignments 456
Index 457
 Visual Walkthrough
xii Contents

4.2 Stack Operations 40

4.3 Applications 43
Summary 48
Illustrative Problems 49
Review Questions 54
Programming Assignments 55
5. Queues 56
5.1 Introduction 56
5.2 Operations on Queues 57
5.3 Circular Queues 62
The book is conveniently organized into five
5.4 Other Types of Queues 66
5.5 Applications 71
Summary 75
parts to favor selection of topics suiting the level
Illustrative Problems 76
Review Questions 81
Programming Assignments 82
of the course offered.
Part II
6. Linked Lists 84
6.1 Introduction 84
6.2 Singly Linked Lists 87
6.3 Circularly Linked Lists 93
6.4 Doubly Linked Lists 98
6.5 Multiply Linked Lists 103
6.6 Applications 105
Summary 112
Illustrative Problems 113
Review Questions 119
Programming Assignments 121
7. Linked Stacks and Linked Queues 123
7.1 Introduction 123
7.2 Operations on Linked Stacks and Linked Queues 124
7.3 Dynamic Memory Management and Linked Stacks 130
7.4 Implementation of Linked Representations 132
7.5 Applications 133
Summary 137
Illustrative Problems 137
Review Questions 148
Programming Assignments 149 Chapter
Part III
8. Trees and Binary Trees 151
8.1 Introduction 151
8.2 Trees: Definition and Basic Terminologies 151
8.3 Re resentation of Trees 153
Linked Lists
6
6.1 Introduction
6.2 Singly Linked Lists
In Part I of the book we dealt with arrays, stacks and queues which 6.3 Circularly Linked
are linear sequential data structures (of these, stacks and queues Lists
have a linked representation as well, which will be discussed in
Chapter 7) 6.4 Doubly Linked Lists
In this chapter we detail linear data structures having a linked 6.5 Multiply Linked
representation. We first list the demerits of the sequential data Lists
structure before introducing the need for a linked representation. 6.6 Applications
Next, the linked data structures of singly linked list, circularly
linked list, doubly linked list and multiply linked list are
elaborately presented. Finally, two problems, viz., Polynomial
addition and Sparse matrix representation, demonstrating the
application of linked lists are discussed.
Each chapter lists the topics covered.
Introduction 6.1
Drawbacks of sequential data structures
Arrays are fundamental sequential data structures. Even stacks and queues rely on arrays for their
representation and implementation. However, arrays or sequential data structures in general,
suffer from the following drawbacks:
(i) inefficient implementation of insertion and deletion operations and
(ii) inefficient use of storage memory.
Let us consider an array A[1 : 20]. This means a contiguous set of twenty memory locations
have been made available to accommodate the data elements of A. As shown in Fig. 6.1(a), let us
suppose the array is partially full. Now, to insert a new element 108 in the position indicated, it
is not possible to do so without affecting the neighbouring data elements from their positions.
Methods such as making use of a temporary array (B) to hold the data elements of A with 108
inserted at the appropriate position or making use of B to hold the data elements of A which
follow 108, before copying B into A, call for extensive data movement which is computationally
expensive. Again, attempting to delete 217 from A calls for the use of a temporary array B to hold
the elements with 217 excluded, before copying B to A. (Fig. 6.1)

Chapter-end summary for use as

Summary
quick reference.
Ø Hash tables are ideal data structures for dictionaries. They favor efficient storage and
retrieval of data lists which are linear in nature.
Ø A hash function is a mathematical function which maps keys to positions in the hash tables
known as buckets. The process of mapping is called hashing. Keys which map to the same
bucket are called as synonyms. In such a case a collision is said to have occurred. A bucket
may be divided into slots to accommodate synonyms. When a bucket is full and a synonym
is unable to find space in the bucket then an overflow is said to have occurred.
Ø The characteristics of a hash function are that it must be easy to compute and at the same
time minimize collisions. Folding, truncation and modular arithmetic are some of the
commonly used hash functions.
Ø A hash table could be implemented using a sequential data structure such as arrays. In
such a case, the method of handling overflows where the closest slot that is vacant is
utilized to accommodate the synonym key is called linear open addressing or linear
probing. However, in course of time, linear probing can lead to the problem of clustering
thereby deteriorating the performance of the hash table to a mere sequential search!
Ø The other alternative methods of handling overflows are rehashing, quadratic probing and
random probing.
 386 Data Structure and Algorithms

Illustrative Problems
Problem 15.1 For the list CHANNELS={ AAXN, ZZEE, CCNN, DDDN HHBO, GGOD,
FFAS, NNDT, SSON, CCAF, NNGE, BBBC, PPRO} trace sequential search for the

.
External Sorting 449

Summary
Ø External sorting deals with sorting of files or lists that are too huge to be accommodated
in the internal memory of the computer and hence need to be stored in external storage
devices such as disks or drums.
Ø The principle behind external sorting is to first make use of any efficient internal sorting
technique to generate runs. These runs are then merged in passes to obtain a single run at
which stage the file is deemed sorted. The merge patterns called for by the strategies, are
influenced by external storage medium on which the runs reside, viz., disks or tapes.
Ø Magnetic tapes are sequential devices built on the principle of audio tape devices. Data is
stored in blocks occurring sequentially. Magnetic disks are random access storage devices.
Data stored in a disk is addressed by its cylinder, track and sector numbers. Extensive Illustrative Problems
Ø Balanced merge sort is a technique that can be adopted on files residing on both disks and
tapes. In its general form, a k-way merging could be undertaken during the runs. For the
efficient management of merging runs, buffer handling and selection tree mechanisms are throughout.
employed.
Ø Balanced k-way merge sort on tapes calls for the use of 2k tapes for an efficient
management of runs. Polyphase merge sort is a clever strategy that makes use of only (k+1)
tapes to perform the k –way merge. The distribution of runs on the tapes follows a
Fibonacci number sequence.
Ø Cascade merge sort is yet another smart strategy which unlike polyphase merge sort
not employ a uniform merge pattern. Each pass makes use of a ‘cascading’ of
merge patterns.

Illustrative Problems
Problem 17.1 The specification for a typical disk storage system is shown in Table I 17.1.
An employee file consisting of 100,000 records is stored on the disk. The employee record structure
and the size of the fields in bytes (shown in brackets) are given below:
Employee Employee Designation Address Basic pay Allowances Deductions Total salary )
number name
(6) (20) (10) (30) (6) (20) (20) (6)
(a) What is the storage space (in terms of bytes) needed to store the employee file in the disk?
(b) What is the storage space (in term of cylinders) needed to store the employee file in the
disk?
Solution:
(a) The size of the employee record = 118 bytes
Number of employee records that can be held in a sector = 512/ 118 = 4 records
Number of sectors needed to hold the whole employee file = 100000/4 = 25,000 sectors

Review Questions include objective-type, short-

Review Questions
answer and long-answer type questions.
1. A minimal superkey is in fact a
(a) secondary key (b) primary key (c) non key (d) none of these
2. State whether true or false:
(i) A cluster index is a sparse index
(ii) A secondary key field with distinct values yields a dense index
(a) (i) true (ii) true (b) (i) true (ii) false (c) (i) false (ii) true (d) (i) false (ii) false
3. An index consisting of variable length entries where each index entry would be of the
form (K, B1≠, B2≠ , B3≠, Bt≠) where Bi≠ ‘s are block addresses of the various records
holding the same value for the secondary key K can occur only in
(a) primary indexing (b) secondary indexing
(c) cluster indexing (d) multilevel indexing

ADT for Queues

Data objects
A finite set of elements of the same type
Operations
l Create an empty queue and initialize front and rear variables of the queue
The ADTs for selective data structures
CREATE ( QUEUE, FRONT, REAR)
l Check if queue QUEUE is empty
CHK_QUEUE_EMPTY (QUEUE ) (Boolean function)
are separately presented for convenience
l Check if queue QUEUE is full
CHK_QUEUE_FULL (QUEUE) (Boolean function)
l Insert ITEM into queue QUEUE
of reference.
ENQUEUE (QUEUE, ITEM)
l Delete element from queue QUEUE and output the element deleted in ITEM
DEQUEUE (QUEUE , ITEM)

Programming Assignments are given Programming Assignment

at the end of each chapter. 1. Write a program to input a binary tree implemented as a linked representation. Execute
Algorithms 8.1–8.3 to perform inorder, postorder and preorder traversals of the binary tree.
2. Implement Algorithm 8.4 to convert an infix expression into its postfix form.
3. Write a recursive procedure to count the number of nodes in a binary tree.
4. Implement a threaded binary tree. Write procedures to insert a node NEW to the left of node
NODE when
(i) the left subtree of NODE is empty, and
(ii) the left subtree of NODE is non-empty.
 Internal Sorting 413

Algorithm 16.7: Procedure for Partition

procedure PARTITION(L, first, last, loc )
/* L[first:last] is the list to be partitioned. loc is the
position where the pivot element finally settles down*/
left = first;
right = last+1;
pivot_elt = L[first]; /* set the pivot element to the first
element in list L*/
while (left < right) do
repeat
left = left+1; /* pivot element moves left to right*/
until L[left] ≥ pivot_elt;
repeat
right = right -1; /* pivot element moves right to left*/
until L[right] £ pivot_elt;
if (left < right) then swap(L[left], L[right]); /*arrows face each
other*/
end
loc = right
swap(L[first], L[right]); /* arrows have crossed each other - exchange
pivot element L[first] with L[right]*/
end PARTITION.

Example 16.13 Let us quick sort the list L = {5, 1, 26, 15, 76, 34, 15}. The various phases of
the sorting process are shown in Fig. 16.8. When the partitioned sublists contain only one element
then no sorting is done. Also in phase 4 of Fig. 16.8 observe how the pivot element 34 exchanges
with itself. The final sorted list is {1, 5, 15, 15, 26, 34, 76}.
Pseudo-code algorithms are given for
Algorithm 16.8: Procedure for Quick Sort
procedure QUICK_SORT(L, first, last )
/* L[first:last] is the unordered list of elements to be
better comprehension
quick sorted. The call to the procedure to sort the
list L[1:n] would be QUICK_SORT(L, 1, n)*/
if (first < last) then
{ PARTITION(L, first, last, loc) ; /* partition the list into two
sublists at loc*/
QUICK_SORT(L, first, loc-1 ); /* quick sort the sublist
L[first,loc-1]*/
QUICK_SORT(L, loc+1, last ); /* quick sort the sublist
L[loc+1, last]*/
}
end QUICK_SORT.
Queues 67
Stability and performance analysis
Quick sort is not a stable sort. During the partitioning process keys which are equal are subject Example 5.3 Let JOB be a queue of jobs to be undertaken at a factory shop floor for service
to exchange and hence undergo changes in their relative orders of occurrence in the sorted list. a machine. Let high (2), medium (1) and low (0) be the priorities accorded to jobs. Let Ji (k)
indicate a job Ji to be undertaken with priority k. The implementations of a priority queue to keep
track of the jobs, using the two methods of implementation discussed above, are illustrated for
a sample set of job arrivals (insertions) and job service completion (deletion).
Opening JOB queue: J1(1) J2 (1) J3 (0)
Operations on the JOB queue in the chronological order :
1. J4 (2) arrives
2. J5 (2) arrives
3. Execute job
4. Execute job
5. Execute job
Implementation of a priority Implementation of a priority Remarks
queue as a cluster of queues queue by sorting queue elements

Extensive examples are given to illustrate Initial

configuration
High priority (2)
JOB Queue
Initial
configuration

theoretical concepts. Medium priority (1)

Opening
JOB queue
JOB Queue J1(1) J2(1) J3(0)
Machine J1(1) J2(1)
service

Low priority (0)

JOB Queue

J3(0)

1. J4(2) arrives High priority (2) 1. J4(2) arrives

JOB Queue
J4(2)

J4(2) J1(1) J2(1) J3(0) Insert J4(2)

Medium priority (1)
JOB Queue
J1(1) J2(1)

Low priority (0)

JOB Queue
J3(0)

(Contd.)

The Online Learning Centre at

[Link]/pai/dsa contains C
programs for algorithms present
in the text, Sample Questions with
Solutions and Web Links.