Vijayalakshmi P. A Textbook of Data Structures and Algorithms Vol 3 2023

Textbook in PDF format

Hash Tables
Dictionaries
Hash table structure
Hash functions
Building hash functions
Linear open addressing
Operations on linear open addressed hash tables
Performance analysis
Other collision resolution techniques with open addressing
Chaining
Operations on chained hash tables
Performance analysis
Applications
Representation of a keyword table in a compiler
Hash tables in the evaluation of a join operation on relational databases
Hash tables in a direct file organization
Illustrative problems
File Organizations
Files
Keys
Basic file operations
Heap or pile organization
Insert, delete and update operations
Sequential file organization
Insert, delete and update operations
Making use of overflow blocks
Indexed sequential file organization
Structure of the ISAM files
Insert, delete and update operations for a naïve ISAM file
Types of indexing
Direct file organization
Illustrative problems
k-d Trees and Treaps
k-d trees: structure and operations
Construction of a k-d tree
Insert operation on k-d trees
Find minimum operation on k-d trees
Delete operation on k-d trees
Complexity analysis and applications of k-d trees
Treaps: structure and operations
Treap structure
Operations on treaps
Complexity analysis and applications of treaps
Illustrative problems
Searching
Linear search
Ordered linear search
Unordered linear search
Transpose sequential search
Interpolation search
Binary search
Decision tree for binary search
Fibonacci search
Decision tree for Fibonacci search
Skip list search
Implementing skip lists
Insert operation in a skip list
Delete operation in a skip list
Other search techniques
Tree search
Graph search
Indexed sequential search
Illustrative problems
Internal Sorting
Bubble sort
Stability and performance analysis
Insertion sort
Stability and performance analysis
Selection sort
Stability and performance analysis
Merge sort
Two-way merging
k-way merging
Non-recursive merge sort procedure
Recursive merge sort procedure
Shell sort
Analysis of shell sort
Quick sort
Partitioning
Quick sort procedure
Stability and performance analysis
Heap sort
Heap
Construction of heap
Heap sort procedure
Stability and performance analysis
Radix sort
Radix sort method
Most significant digit first sort
Performance analysis
Counting sort
Performance analysis
Bucket sort
Performance analysis
Illustrative problems
External Sorting
The principle behind external sorting
External storage devices
Magnetic tapes
Magnetic disks
Sorting with tapes: balanced merge
Buffer handling
Balanced P-way merging on tapes
Sorting with disks: balanced merge
Balanced k-way merging on disks
Selection tree
Polyphase merge sort
Cascade merge sort
Illustrative problems
Divide and Conquer
Principle and abstraction
Finding maximum and minimum
Time complexity analysis
Merge sort
Time complexity analysis
Matrix multiplication
Divide and Conquer-based approach to “high school” method of matrix multiplication
Strassen’s matrix multiplication algorithm
Illustrative problems
Greedy Method
Abstraction
Knapsack problem
Greedy solution to the knapsack problem
Minimum cost spanning tree algorithms
Prim's algorithm as a greedy method
Kruskal's algorithm as a greedy method
Dijkstra's algorithm
Illustrative problems
Dynamic Programming
/ knapsack problem
Dynamic programming-based solution
Traveling salesperson problem
Dynamic programming-based solution
Time complexity analysis and applications of traveling salesperson problem
All-pairs shortest path problem
Dynamic programming-based solution
Time complexity analysis
Optimal binary search trees
Dynamic programming-based solution
Construction of the optimal binary search tree
Time complexity analysis
Illustrative problems
P and NP Class of Problems
Deterministic and nondeterministic algorithms
Satisfiability problem
Conjunctive normal form and Disjunctive normal form
Definition of the satisfiability problem
Construction of CNF and DNF from a logical formula
Transformation of a CNF into a -CNF
Deterministic algorithm for the satisfiability problem
Nondeterministic algorithm for the satisfiability problem
NP-complete and NP-hard problems
Definitions
Examples of NP-hard and NP-complete problems
Cook's theorem
The unsolved problem
Illustrative problems
Summaries of other volumes