Data Structures and Algorithm Analysis in C++

Description

With its focus on creating efficient data structures and algorithms, this comprehensive text helps readers understand how to select or design the tools that will best solve specific problems. It uses Microsoft C++ as the programming language and is suitable for second-year data structure courses and computer science courses in algorithm analysis. Techniques for representing data are presented within the context of assessing costs and benefits, promoting an understanding of the principles of algorithm analysis and the effects of a chosen physical medium. The text also explores tradeoff issues, familiarizes readers with the most commonly used data structures and their algorithms, and discusses matching appropriate data structures to applications. The author offers explicit coverage of design patterns encountered in the course of programming the book's basic data structures and algorithms. Numerous examples appear throughout the text. Data Structures and Algorithm Analysis in C++ 3rd Edition Contents Preface PART I: Preliminaries 1: Data Structures and Algorithms 1.1 A Philosophy of Data Structures 1.2 Abstract Data Types and Data Structures 1.3 Design Patterns 1.4 Problems, Algorithms, and Programs 1.5 Further Reading 1.6 Exercises 2: Mathematical Preliminaries 2.1 Sets and Relations 2.2 Miscellaneous Notation 2.3 Logarithms 2.4 Summations and Recurrences 2.5 Recursion 2.6 Mathematical Proof Techniques 2.7 Estimation 2.8 Further Reading 2.9 Exercises 3:Algorithm Analysis 3.1 Introduction 3.2 Best, Worst, and Average Cases 3.3 A Faster Computer, or a Faster Algorithm? 3.4 Asymptotic Analysis 3.5 Calculating the Running Time for a Program 3.6 Analyzing Problems 3.7 Common Misunderstandings 3.8 Multiple Parameters 3.9 Space Bounds 3.10 Speeding Up Your Programs 3.11 Empirical Analysis 3.12 Further Reading 3.13 Exercises 3.14 Projects PART II: Fundamental Data Structures 4: Lists, Stacks, and Queues 4.1 Lists 4.2 Stacks 4.3 Queues 4.4 Dictionaries 4.5 Further Reading 4.6 Exercises 4.7 Projects 5: Binary Trees 5.1 Denitions and Properties 5.2 Binary Tree Traversals 5.3 Binary Tree Node Implementations 5.4 Binary Search Trees 5.5 Heaps and Priority Queues 5.6 Human Coding Trees 5.7 Further Reading 5.8 Exercises 5.9 Projects 6: Non-Binary Trees 6.1 General Tree Denitions and Terminology 6.2 The Parent Pointer Implementation 6.3 General Tree Implementations 6.4 K-ary Trees 6.5 Sequential Tree Implementations 6.6 Further Reading 6.8 Projects PART III: Sorting and Searching 7: Internal Sorting 7.1 Sorting Terminology and Notation 7.2 Three (n2) Sorting Algorithms 7.3 Shellsort 7.4 Mergesort 7.5 Quicksort 7.6 Heapsort 7.7 Binsort and Radix Sort 7.8 An Empirical Comparison of Sorting Algorithms 7.9 Lower Bounds for Sorting 7.10 Further Reading 7.11 Exercises 7.12 Projects 8: File Processing and ExternalSorting 8.1 Primary versus Secondary Storage 8.2 Disk Drives 8.3 Bu ers and Bu er Pools 8.4 The Programmer's View of Files 8.5 External Sorting 8.6 Further Reading 8.7 Exercises 8.8 Projects 9: Searching 9.1 Searching Unsorted and Sorted Arrays 9.2 Self-Organizing Lists 9.3 Bit Vectors for Representing Sets 9.4 Hashing 9.5 Further Reading 9.6 Exercises 9.7 Projects 10: Indexing 10.1 Linear Indexing 10.2 ISAM 10.3 Tree-based Indexing 10.4 2-3 Trees 10.5 B-Trees 10.6 Further Reading 10.7 Exercises 10.8 Projects PART IV: Advanced Data Structures 11: Graphs 11.1 Terminology and Representations 11.2 Graph Implementations 11.3 Graph Traversals 11.4 Shortest-Paths Problems 11.5 Minimum-Cost Spanning Trees 11.6 Further Reading 11.7 Exercises 11.8 Projects 12: Lists and Arrays Revisited 12.1 Multilists 12.2 Matrix Representations 12.3 Memory Management 12.4 Further Reading 12.5 Exercises 12.6 Projects 13: Advanced Tree Structures 13.1 Tries 13.2 Balanced Trees 13.3 Spatial Data Structures 13.4 Further Reading 13.5 Exercises 13.6 Projects PART V: Theory of Algorithms 14: Analysis Techniques 14.1 Summation Techniques 14.2 Recurrence Relations 14.3 Amortized Analysis 14.4 Further Reading 14.5 Exercises 14.6 Projects 15: Lower Bounds 15.1 Introduction to Lower Bounds Proofs 15.2 Lower Bounds on Searching Lists 15.3 Finding the Maximum Value 15.4 Adversarial Lower Bounds Proofs 15.5 State Space Lower Bounds Proofs 15.6 Finding the ith Best Element 15.7 Optimal Sorting 15.8 Further Reading 15.9 Exercises 15.10 Projects 16: Patterns of Algorithms 16.1 Dynamic Programming 16.2 Randomized Algorithms 16.3 Numerical Algorithms 16.4 Further Reading 16.5 Exercises 16.6 Projects 17: Limits to Computation 17.1 Reductions 17.2 Hard Problems 17.3 Impossible Problems 17.4 Further Reading 17.5 Exercises 17.6 Projects PART VI: APPENDIX AUtility Functions Bibliography Index