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

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

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...

Descripción completa

Detalles Bibliográficos
Otros Autores: Pai, G. A. Vijayalakshmi, author (author)
Formato: Libro electrónico
Idioma:Inglés
Publicado: Hoboken, NJ : John Wiley & Sons, Inc [2023]
Edición:[First edition]
Colección:Computer engineering series (London, England)
Materias:
Data structures (Computer science)
Computer algorithms.
Ver en Biblioteca Universitat Ramon Llull:https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009724221806719
Tabla de Contenidos:
  • 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.

Ejemplares similares