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

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