Data Structures and Algorithm Analysis (C++)


This book describes many techniques for representing data. These techniques are presented within the context of the following principles:

1. Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation for the significant effects of the physical medium employed (e.g., data stored on disk versus main memory).

2. Related to costs and benefits is the notion of tradeoffs. For example, it is quite common to reduce time requirements at the expense of an increase in space requirements, or vice versa. Programmers face tradeoff issues regularly in all phases of software design and implementation, so the concept must become deeply ingrained.

3. Programmers should know enough about common practice to avoid reinventing the wheel. Thus, programmers need to learn the commonly used data structures, their related algorithms, and the most frequently encountered design patterns found in programming.

4. Data structures follow needs. Programmers must learn to assess application needs first, then find a data structure with matching capabilities. To do this requires competence in Principles 1, 2, and 3.

As I have taught data structures through the years, I have found that design issues have played an ever greater role in my courses. This can be traced through the various editions of this textbook by the increasing coverage for design patterns and generic interfaces. The first edition had no mention of design patterns. The second edition had limited coverage of a few example patterns, and introduced the dictionary ADT and comparator classes. With the third edition, there is explicit coverage of some design patterns that are encountered when programming the basic data structures and algorithms covered in the book

Download the file

  • Preliminaries
    • Data Structures and Algorithms
    • Mathematical Preliminaries
    • Algorithm Analysis
  • Fundamental Data Structures
    • Lists, Stacks, and Queues
    • Binary Trees
    • Non-Binary Trees
  • Sorting and Searching
    • Internal Sorting
    • File Processing and External Sorting
    • Searching
    • Indexing
    • Advanced Data Structures
    • Graphs
    • Lists and Arrays Revisited
  • Advanced Tree Structures
  • Theory of Algorithms
    • Analysis Techniques
    • Lower Bounds
    • Patterns of Algorithms
    • Limits to Computation