Practical Introduction to Data Structures and Algorithm Analysis (C++ Edition)
Appropriate for a sophomore/junior level second course in data structures and algorithms analysis (CS7) in departments of Computer Science.This book thoroughly covers key data structures at the undergraduate level. With a focus on how to assess costs and benefits, it teaches students how to create efficient data structures and algorithms and how to adopt to new design challenges. Students are taught how to assess applications needs to find data structures with matching capabilities.
- Hardback | 512 pages
- 182 x 234 x 26mm | 879.98g
- 06 Sep 2000
- Pearson Education (US)
- United States
- 2nd edition
Back cover copy
In this eagerly anticipated revision, Clifford A. Shaffer provides a thorough and comprehensive treatment of fundamental data structures and the principles of algorithm analysis. The author focuses on teaching students and practitioners how to create "efficient" data structures and algorithms and to understand the principles required to select or design the data structure that will best solve the problem. The integrated treatment of algorithm analysis, file processing, and efficiency places this book in a class of its own. Features: Algorithm analysis techniques are presented throughout the text. Analysis is closely tied to the needs of practicing programmers and students. It is not presented as theory for theory's sake. Coverage of basic file processing techniques as an integral component of efficient data structures and algorithm analysis. C++ is used as a tool to illustrate data structure concepts with clear, simple-to-understand examples. All programming examples are actual C++ code. This book presents each data structure and algorithm as having costs and benefits, and provides the reader with a thorough understanding of how to assess the costs and benefits, including space comparisons for data structures, space/time trade-offs, and special-purpose uses of data structures or algorithms. New to this Edition: Completely rewritten coding examples that are clear and illustrative. Extensive use of object-oriented programming techniques. Expanded coverage of recursion, Dictionary ADT, balanced tress, and buffer pools. More emphasis on techniques for object-oriented program design. More exercises and examples. Close to 350 problems and projects.
Table of contents
(NOTE: Each chapter concludes with Further Readings, Exercises, and/or Projects.)I. PRELIMINARIES. 1. Data Structures and Algorithms. A Philosophy of Data Structures. Abstract Data Types and Data Structures. Problems, Algorithms, and Programs.2. Mathematical Preliminaries. Sets and Relations. Miscellaneous Notation. Logarithms. Recursion. Summations and Recurrences. Mathematical Proof Techniques. Estimating.3. Algorithm Analysis. Introduction. Best, Worst, and Average Cases. A Faster Computer, or a Faster Algorithm? Asymptotic Analysis. Calculating the Running Time of a Program. Analyzing Problems. Common Misunderstandings. Multiple Parameters. Space Bounds. Some Practical Considerations.II. FUNDAMENTAL DATA STRUCTURES. 4. Lists, Stacks, and Queues. Lists. The Dictionary ADT. Stacks. Queues.5. Binary Trees. Definitions and Properties. Binary Tree Traversals. Binary Tree Node Implementations. Binary Search Trees. Heaps and Priority Queues. Huffman Coding Trees.6. Non-Binary Trees. General Tree Definitions and Terminology. The Parent Pointer Implementation. General Tree Implementations. K -ary Trees. Sequential Tree Implementations.III. SORTING AND SEARCHING. 7. Internal Sorting. Sorting Terminology and Notation. Three ...Q(n2) Sorting Algorithms. Shellsort. Quicksort. Mergesort. Heapsort. Binsort and Radix Sort. An Empirical Comparison of Sorting Algorithms. Lower Bounds for Sorting.8. File Processing and External Sorting. Primary versus Secondary Storage. Disk Drives. Buffers and Buffer Pools. The Programmer's View of Files. External Sorting. Simple Approaches to External Sorting. Replacement Selection. Multiway Merging.9. Searching. Searching Sorted Arrays. Self-Organizing Lists. Searching in Sets. Hashing.10. Indexing. Linear Indexing. ISAM. Tree Indexing. 2-3 Trees. B-Trees.IV. APPLICATIONS AND ADVANCED TOPICS. 11. Graphs. Terminology and Representations. Graph Implementations. Graph Traversals. Shortest-Paths Problems. Minimum-Cost Spanning Trees.12. Lists and Arrays Revisited. Skip Lists. Multilists. Matrix Representations. Memory Management.13. Advanced Tree Structures. Tries. Balanced Trees. Spatial Data Structures.14. Analysis Techniques. Summation Techniques. Recurrence Relations. Amortized Analysis.15. Limits to Computation. Reductions. Hard Problems. Impossible Problems.V. APPENDIX. Utility Functions. Bibliography. Index.