A Textbook of Data Structures and Algorithms, Volume 3: Mastering Advanced Data Structures and Algorithm Design Strategies

✍ Scribed by G. A. Vijayalakshmi Pai

• Publisher: Wiley-ISTE
• Year: 2023
• Tongue: English
• Leaves: 356
• Series: Computer Engineering Series
• Category: Library

✦ Table of Contents

Cover
Title Page
Copyright Page
Contents
Preface
Acknowledgments
Chapter 13. Hash Tables
13.1. Introduction
13.1.1. Dictionaries
13.2. Hash table structure
13.3. Hash functions
13.3.1. Building hash functions
13.4. Linear open addressing
13.4.1. Operations on linear open addressed hash tables
13.4.2. Performance analysis
13.4.3. Other collision resolution techniques with open addressing
13.5. Chaining
13.5.1. Operations on chained hash tables
13.5.2. Performance analysis
13.6. Applications
13.6.1. Representation of a keyword table in a compiler
13.6.2. Hash tables in the evaluation of a join operation on relational databases
13.6.3. Hash tables in a direct file organization
13.7. Illustrative problems
Chapter 14. File Organizations
14.1. Introduction
14.2. Files
14.3. Keys
14.4. Basic file operations
14.5. Heap or pile organization
14.5.1. Insert, delete and update operations
14.6. Sequential file organization
14.6.1. Insert, delete and update operations
14.6.2. Making use of overflow blocks
14.7. Indexed sequential file organization
14.7.1. Structure of the ISAM files
14.7.2. Insert, delete and update operations for a naïve ISAM file
14.7.3. Types of indexing
14.8. Direct file organization
14.9. Illustrative problems
Chapter 15. k-d Trees and Treaps
15.1. Introduction
15.2. k-d trees: structure and operations
15.2.1. Construction of a k-d tree
15.2.2. Insert operation on k-d trees
15.2.3. Find minimum operation on k-d trees
15.2.4. Delete operation on k-d trees
15.2.5. Complexity analysis and applications of k-d trees
15.3. Treaps: structure and operations
15.3.1. Treap structure
15.3.2. Operations on treaps
15.3.3. Complexity analysis and applications of treaps
15.4. Illustrative problems
Chapter 16. Searching
16.1. Introduction
16.2. Linear search
16.2.1. Ordered linear search
16.2.2. Unordered linear search
16.3. Transpose sequential search
16.4. Interpolation search
16.5. Binary search
16.5.1. Decision tree for binary search
16.6. Fibonacci search
16.6.1. Decision tree for Fibonacci search
16.7. Skip list search
16.7.1. Implementing skip lists
16.7.2. Insert operation in a skip list
16.7.3. Delete operation in a skip list
16.8. Other search techniques
16.8.1. Tree search
16.8.2. Graph search
16.8.3. Indexed sequential search
16.9. Illustrative problems
Chapter 17. Internal Sorting
17.1. Introduction
17.2. Bubble sort
17.2.1. Stability and performance analysis
17.3. Insertion sort
17.3.1. Stability and performance analysis
17.4. Selection sort
17.4.1. Stability and performance analysis
17.5. Merge sort
17.5.1. Two-way merging
17.5.2. k-way merging
17.5.3. Non-recursive merge sort procedure
17.5.4. Recursive merge sort procedure
17.6. Shell sort
17.6.1. Analysis of shell sort
17.7. Quick sort
17.7.1. Partitioning
17.7.2. Quick sort procedure
17.7.3. Stability and performance analysis
17.8. Heap sort
17.8.1. Heap
17.8.2. Construction of heap
17.8.3. Heap sort procedure
17.8.4. Stability and performance analysis
17.9. Radix sort
17.9.1. Radix sort method
17.9.2. Most significant digit first sort
17.9.3. Performance analysis
17.10. Counting sort
17.10.1. Performance analysis
17.11. Bucket sort
17.11.1. Performance analysis
17.12. Illustrative problems
Chapter 18. External Sorting
18.1. Introduction
18.1.1. The principle behind external sorting
18.2. External storage devices
18.2.1. Magnetic tapes
18.2.2. Magnetic disks
18.3. Sorting with tapes: balanced merge
18.3.1. Buffer handling
18.3.2. Balanced P-way merging on tapes
18.4. Sorting with disks: balanced merge
18.4.1. Balanced k-way merging on disks
18.4.2. Selection tree
18.5. Polyphase merge sort
18.6. Cascade merge sort
18.7. Illustrative problems
Chapter 19. Divide and Conquer
19.1. Introduction
19.2. Principle and abstraction
19.3. Finding maximum and minimum
19.3.1. Time complexity analysis
19.4. Merge sort
19.4.1. Time complexity analysis
19.5. Matrix multiplication
19.5.1. Divide and Conquer-based approach to “high school” method of matrix multiplication
19.5.2. Strassen’s matrix multiplication algorithm
19.6. Illustrative problems
Chapter 20. Greedy Method
20.1. Introduction
20.2. Abstraction
20.3. Knapsack problem
20.3.1. Greedy solution to the knapsack problem
20.4. Minimum cost spanning tree algorithms
20.4.1. Prim's algorithm as a greedy method
20.4.2. Kruskal's algorithm as a greedy method
20.5. Dijkstra's algorithm
20.6. Illustrative problems
Chapter 21. Dynamic Programming
21.1. Introduction
21.2. 0/1 knapsack problem
21.2.1. Dynamic programming-based solution
21.3. Traveling salesperson problem
21.3.1. Dynamic programming-based solution
21.3.2. Time complexity analysis and applications of traveling salesperson problem
21.4. All-pairs shortest path problem
21.4.1. Dynamic programming-based solution
21.4.2. Time complexity analysis
21.5. Optimal binary search trees
21.5.1. Dynamic programming-based solution
21.5.2. Construction of the optimal binary search tree
21.5.3. Time complexity analysis
21.6. Illustrative problems
Chapter 22. P and NP Class of Problems
22.1. Introduction
22.2. Deterministic and nondeterministic algorithms
22.3. Satisfiability problem
22.3.1. Conjunctive normal form and Disjunctive normal form
22.3.2. Definition of the satisfiability problem
22.3.3. Construction of CNF and DNF from a logical formula
22.3.4. Transformation of a CNF into a 3-CNF
22.3.5. Deterministic algorithm for the satisfiability problem
22.3.6. Nondeterministic algorithm for the satisfiability problem
22.4. NP-complete and NP-hard problems
22.4.1. Definitions
22.5. Examples of NP-hard and NP-complete problems
22.6. Cook's theorem
22.7. The unsolved problem 𝑷 ? = 𝑵𝑷
22.8. Illustrative problems
References
Index
Summaries of other volumes
EULA