Abstract data types (ADTs) are an important and well-established programming discipline on which much current software, including object-oriented programs, is based. This text uses abstract data types to teach abstraction, computational complexity, and parallel computation. The text assumes a working knowledge of a high-level programming language such as Ada or Pascal; the ability to implement and use stacks, queues, and binary search trees; and the ability to write sorting and recursive algorithms.
The first three chapters are devoted to the definition and brief illustration of the main concepts: ADT specification and implementation, implementation correctness, computational complexity, and parallel computation. The next nine chapters discuss about 15 ADTs of general utility in manipulating data structures, such as set, stack, list, and graph. Each presentation of an ADT shows its specification; shows one or more implementations of the specification using a pseudo-language based on Ada, Modula-2, and Pascal; discusses the implementation’s correctness and computational complexity; and presents one or more applications of the ADT (such as use of an ADT to implement a second ADT or to solve a larger problem). The final chapter gives the high-level-language programmer an introduction to memory management.
ADTs are an excellent vehicle for teaching abstraction. The text takes the axiomatic approach for their specification. The alternative approach--abstract models--is defined and illustrated, but implementation is not mentioned. A discussion of the relative merits of the two specification methods would have been helpful to students puzzled by the abstruseness of formal axioms as compared with abstract models.
For implementation bases, the authors occasionally use ADTs formally specified elsewhere in the text, but more often they rely on informally defined bases. Chapter 1 begins badly by trying to show the correctness of a stack implementation while the implementation itself is being described. This apparent disregard for implementation is repeated in chapter 2, where the complexity of three implementations of a list is discussed without the benefit of implementation details, which do not appear until chapter 3. With a little more thought on the organization of the initial chapters, the authors could have done a good job of illustrating the implementation process, including the design and use of program modules, before attempting to discuss correctness and complexity.
To show implementation correctness, chapter 1 uses the customary procedure for demonstrating transformation isomorphism. Correctness is discussed for 6 of the approximately 25 implementations presented, and exercises are provided for proving correctness of several other implementations. Despite its focus on the axiomatic method of specification, nothing is said about the problem of determining the completeness of a set of axioms.
ADTs also prove useful for teaching computational complexity. Chapter 2 introduces “big O” notation for expressing algorithm complexity, and works through a number of examples in detail. Chapter 11 provides a good discussion of computational complexity in a broader context. The discussion is motivated by complex graph processing problems.
Parallel computation is not as fruitfully explored from the ADT perspective as are abstraction and computational complexity. There is little connection made to ADTs in the discussion of parallel computation; in particular, none of the ADT implementations uses parallel algorithms. Chapter 3 provides a conceptual basis for understanding parallelism at the hardware and application levels, and several later chapters provide extended examples of parallel algorithms, including algorithms for searching in unsorted and sorted arrays, sorting, and depth-first and breadth-first graph traversals.
While the book’s expository style is informal and deliberate (almost in the style of a lecture), and is student-friendly, it can foster the inappropriately casual use of terminology. For example, the term “list” is sometimes used to mean a kind of data structure, sometimes a specific ADT, and sometimes the implementation of a specific ADT. The style also results in some explanations that are too long and detailed for college students.
Each chapter ends with a comprehensive set of exercises. Answers to many of the exercises are included in an appendix, and an instructor’s guide contains answers to all non-coding exercises. An appendix describes the use of Mathematica to display the results of operations on axiomatically specified ADTs, and a PC diskette contains implementations of each ADT covered in the text, coded in Pascal, Ada, C++, and Michael.
