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