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.
Author(s): Clifford A. Shaffer
Edition: 3
Publisher: Dover Publications
Year: 2011
Language: English
Pages: 624
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 De nitions 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 Hu man Coding Trees
5.7 Further Reading
5.8 Exercises
5.9 Projects
6: Non-Binary Trees
6.1 General Tree De nitions 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
