Cover
Title Page
Copyright Page
Dedication
Contents
Preface
CHAPTER 1 INTRODUCTION TO DATA STRUCTURES
Overview
Need for Data Structures
Definitions
Types
Data Type
Abstract Data Type (ADT)
Advantages of ADT
Pre and Post Conditions
Data Structures
Types of Data Structures
Choice of Data Structures
Definitions Related to Data Structures
Summary
Solved Exercises
Review Questions
Exercises
CHAPTER 2 ALGORITHM ANALYSIS
Overview
Introduction
Problem Solving
Categories of Problem Solving
Problem Solving Strategies
Modular Design
Bottom-up Design
Top-down Design
Implementation of Algorithms
Choice of Data Structure
Common Errors in Implementation
Testing
Functional Testing
Performance Testing
Verification
Loop Invariants
Program Verification – An example
Verification of Programs Using Arrays
Algorithm Analysis
Operations Count
Time Complexity Classes
Asymptotic Analysis
Asymptotic Upper Bound–Big O
Summary
Review Questions
Exercises
CHAPTER 3 ARRAYS
Overview
Introduction
Range of an Array
Primitive Operations
Element Access in an Array
Addressing Function
One-Dimensional Array
Two-Dimensional Array
Storage Representation of 2D Arrays
Multidimensional Arrays
Addressing Function of a 3D Array
Special Types of Matrices
Lower Triangular Matrices
Upper Triangular Matrices
Tridiagonal Matrix
Sparse Matrices
Strings
Variable Length Strings
String Operations
Substring
Records
Variant Records
Summary
Solved Exercise
Exercises
Programming Exercises
CHAPTER 4 LINKED LISTS
Overview
Introduction
Memory Allocation
Benefits of Linked Lists
Limitations of Linked Lists
Types
Basic Operations in Linked List
ADT List
Singly Linked Lists
C Program
Simple Algorithms on Linked Lists
Print the Elements in a List
Insert a Node in a Sorted List
Copy a List
Concatenation of Two Lists
Deletion of a Node
Circular Linked Lists
Count the Number of Nodes in a Circularly Linked List
Print the Elements of a Circularly Linked List
Doubly Linked Lists
Print the Elements in a DLL
Insertion in a DLL
Deletion in DLL
Circular Doubly Linked List
Initialization of a Circular DLL
Header (or Sentinel Node)
Cursor Implementation of Linked Lists
Initialization of Cursor
Allocate a Node
Deallocation of Node from the List
Initialization of a List
Checking for Null List
C function to Check for Null List
Insert a Node at the Head of a List
Insert a Value After a Given Key
Deletion of a Value From a List
Print the Values of a List
Performance Comparison of Various Types of Lists
Multiply Linked Lists
Sparse Matrix Representation
Applications of Linked Lists
Polynomial Representation
Polynomial Addition
Representation of Polynomials With Multi Variables
Summary
Review Questions
Exercises
CHAPTER 5 STACKS
Overview
Introduction
ADT Stack
Create (S)
Push (S, Element)
Pop (S)
ShowTop(S)
isEmpty(S)
Implementation of Stack
Array Implementation of Stack
Linked List Implementation of Stack
Definition of a Stack Using Linked Lists
Reversing a List
Palindrome Checking
Applications of Stack
Well Formedness of Parenthesis
Syntax Checking using Stacks
Infix, Prefix and Postfix Forms of Expressions
Conversion of Infix Expression to Postfix Form
Steps in Conversion of Infix Expression to Postfix Notation
Evaluation of Postfix Expressions
Algorithm to Evaluate Postfix Expression
Evaluation of Recursive Functions
Solving Tower of Hanoi Problem
Recurrence Relation for Tower of Hanoi Problem
Solving Maze Problem
Solved Exercises
Exercises
Programming Exercises
CHAPTER 6 QUEUES
Overview
Introduction
Implementation of Queues
Basic Operations on Queues
Implementation of Basic Operations on Array-Based Implementation ofQueues
Creation
Insertion
Deletion
Implementations of basic operations on linked list-based implementation of queues
Creation
Insertion
Deletion
Implementation of Queue Operations Using Stacks
Enqueue Operation
Dequeue Operation
Round Robin Algorithm
Priority Queue
Limitations of Linear Array-Based Queues
Circular Queues
Dequeue
Input Restricted Dequeue
Output Restricted Dequeue
Applications of Queues
Summary
Review Questions
Exercises
CHAPTER 7 TREES
Overview
Introduction
Binary Trees
Types of Binary Trees
Strictly Binary Tree
Complete Binary Tree
Almost Complete Binary Tree
Skew Trees
Number of Nodes in Binary Trees
Strictly Binary Tree
Complete Binary Tree
Almost Complete Binary Tree
Skew Trees
Binary Trees
Operations on Binary Trees
Inorder Traversal
Pre Order Traversal
Post Order Traversal
Breadth First Traversal
Representation of Binary Trees
Linear Representation
Linked Representation
Node Representation of Binary Trees
C Function to Create a Binary Tree Node
Construction of a Simple Binary Tree
Function to Count the Number of Nodes in a Binary Tree
Function to Determine the Depth of the Tree
Identical Trees
Binary Tree Traversal in C
Inorder Traversal
Non-Recursive Algorithm for Preorder Traversal
Applications of Binary Trees
Huffman Coding
Decoding
Heap
Properties of Heap
Representation of Heap
Operations on a Heap
Deletion
Threaded Binary Trees
Inorder Traversal of Threaded Binary Trees
Representation of Right In–Threaded Trees
Expression Trees
Evaluating an Expression Tree
Representing General Trees Using Binary Trees
Solved Exercises
Exercises
Programming Assignments
CHAPTER 8 BINARY SEARCH TREES
Overview
Introduction
Creation of a BST
Searching an Element in BST
Complexity of Searching in BST
Ordering Elements in BST
Minimum Element in a BST
Maximum Element in a BST
Deletion of an Element in a BST
Predecessor of a Node in a BST
Successor of a Node
Application of BST
BST with Duplicates
Bin-Packing Problem
Indexed Binary Search Trees
Indexed Search in Indexed BST
Summary
Solved Exercises
Exercises
Programming Exercises
CHAPTER 9 BALANCED SEARCH TREES
Overview
Adelson Velskii Landis (Avl) Trees
Height of AVL Tree
Operations in AVL Tree
Single Right Rotation (SRR)
Single Left Rotation (SLR)
Double Left Right Rotation (DLR)
Double Right Left Rotation
Deletion of Node
Illustration of Balancing of Nodes in an AVL Tree
Illustration of Deletion on AVL Trees
Multiway Search Tree
B Trees
Operations on B-Tree
Searching
Insertion
Deletion
B+ Tree
Search operation
Insertion
Deletion
Situation 1:
Situation 2:
Trie
Searching
Summary
Review Questions
Exercises
CHAPTER 10 HASHING
Overview
Introduction
Hash Functions
Direct Method
Division-Reminder Method
Multiplicative Hashing
Mid-Square Method
Digit Analysis Method
Length Dependent Method
Folding Method
Collision Resolution Techniques
Linear Probing
Double Hashing
Chaining
Overflow Area
Hashing
Open Addressing
Quadratic probing
Separate Chaining
Extendible Hashing
Find Operation
Insertion
Performance of Hashing
Theoretical Estimates of Collision Resolution Techniques
Limitations of Hashing
Summary
Review Questions
Exercises
CHAPTER 11 SORTING AND SEARCHING
Overview
Sorting
General Background of Sorting
Classification of Sorting Algorithms
Classification Based on Structure of the Algorithm
Classification Based on Computational Complexity
Classification Based on Stability of Sorting
Classification Based on Memory Usage
Selection of Sorting Method
Complexity Analysis
Selection Sort
Binary Tree Sort
Heap Sort
Heap Sort Procedure
Complexity
Simple Insertion
Shell Sort
Counting Sort
Complexity of Counting Sort
Merge Sort
Radix Sort
Complexity of Radix Sort
Bucket Sort
Complexity of Bucket Sort
Sorting Using Binary Search Tree
Sorting on Tapes
Polyphase Sorting
Sorting on Disks Using Merging
Searching
Complexity of Sequential Search
Binary Search
Complexity of Binary Search
Searching Using BST
Complexity of Searching in BST
Summary
Solved Exercises
Review Questions
Exercises
Programming Assignments
CHAPTER 12 GRAPHS
Overview
Introduction
Representation of Graphs
Adjacency Matrix
Adjacency Lists
Operations on Graphs
Insertion
Deletion
Traversal
Breadth First Search (BFS)
Data Structures Used in BFS Algorithm
BFS on Adjacency Matrix Representation of a Graph
BFS on Adjacency List Representation of a Graph
Complexity
BFS Tree
Depth First Search (DFS)
DFS (G)
DFS_VERTEX(u)
Complexity
Shortest Path Algorithm
Shortest Path in an Unweighted Graph
Shortest Path on a Weighted Graph
Dijkstra’s Algorithm
Implementation of Dijkstra’s Algorithm
Complexity Analysis
All Pairs Shortest Path
Minimum Spanning Tree
Kruskal’s Algorithm
Prim’s Algorithm
Kruskal’s Algorithm
Data Structures for Implementation of Kruskal’s Algorithm
Complexity of Algorithm
Prim’s Algorithm
Topological Sort
Complexity of Algorithm
Biconnected Components
Euler Circuit
Hamilton Circuits
Solved Exercises
Review Questions
Exercises
CHAPTER 13 INTRODUCTION TO NP COMPLETE PROBLEMS
Overview
Introduction
Decidability
Complexity Class of Problems
Examples of Problems
Simple Path in a Graph
Halting Problem
NP Complete Problems
Solving NP Complete Problems
Approximation
Probabilistic
Heuristic
Special Algorithm
Polynomial Reduction
Polynomial Transformation
NP Completeness
Is P = NP?
P ⊆ NP
Cooks Theorem
Clique Problem is NP Complete
Summary
Review Questions
Exercises
Index
Twitter
Facebook
WhatsApp
LinkedIn