Details

Autor(en) / Beteiligte

• Pai, G. A. Vijayalakshmi,

Titel

A textbook of data structures and algorithms : mastering advanced data structures and algorithm design strategies. Volume 3

Auflage

[First edition]

Ort / Verlag

Hoboken, NJ : John Wiley & Sons, Inc.,

Erscheinungsjahr

[2023]

Link zum Volltext

• Wiley Online Library - AutoHoldings Books

Beschreibungen/Notizen

• 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.
• Data structures and algorithms is a fundamental course in Computer Science, which enables learners across any discipline to develop the much-needed foundation of efficient programming, leading to better problem solving in their respective disciplines. A Textbook of Data Structures and Algorithms is a textbook that can be used as course material in classrooms, or as self-learning material. The book targets novice learners aspiring to acquire advanced knowledge of the topic. Therefore, the content of the book has been pragmatically structured across three volumes and kept comprehensive enough to help them in their progression from novice to expert. With this in mind, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language. It includes 181 illustrative problems and 276 review questions to reinforce a theoretical understanding and presents a suggestive list of 108 programming assignments to aid in the implementation of the methods covered.
• Description based on print version record.