Browse Books

Reviewer: Doris C. Appleby

Even the simplest program can be considered an application of data structures, but courses and texts with the words in the title have long been part of the computer science curriculum. The recommended curriculum is in the process of revision; guidelines for a new first course appeared in 1984, and those for the second course in 1985. In Curriculum '78 [1], there were three prerequisites to the data structures course, CS7. Much of the material from that syllabus is now included in the new CS2. The authors for both the new CS1 [2] and CS2 [3] curricula expect that most students “will have taken one or more programming courses in high school,” and that those who haven't will have to do extra work on their own. Existing textbooks reflect this situation, in that most were written for CS7, to be taught at the sophomore or junior level. Many texts for the new CS1 have appeared in the last few months, and publishers promise new choices for CS2 in the near future. It is also anticipated that a new syllabus for CS7 will be more advanced when it appears. Thus, we currently have data structures texts that are too hard for CS2 students, and too elementary for an upper-level data structures course. In addition to expecting very well-prepared freshmen, both the new CS1 and CS2 are organized for a four-credit format, including a two hour laboratory each week for at least CS1. However, it is quite possible that many students will have studied nothing but BASIC in high school, and that many colleges will continue to offer three-credit courses, with or without labs. Thus, data structures could continue to be taught at the same level anticipated in Curriculum '78, with two or three rather elementary prerequisite courses. The five books chosen for review are what might be considered “semi-advanced” undergraduate texts in data structures. They are advanced in that each covers considerable material past that suggested for CS2, but are accessible to students with less background than those who have completed the full CS2 syllabus. None are entirely suitable for a course based on the new syllabus, or for an advanced CS7, enrolling students who had completed the new CS2. All but one are revisions of older texts to include Pascal. Although all of these books may be superseded by others if the proposed curriculum for CS2 becomes standard, they will be good volumes by which to measure new ones. Some will continue to be available, but none may be widely used in five years. Horowitz and Sahni This text was first published in 1976 as Fundamentals of Data Structures [4]. It has served many students as a “Bible” along with the companion volume, Fundamentals of Computer Algorithms [5], which first appeared in 1978. It was, and is, an effective blend of abstract data structure, proofs of correctness, and algorithmic analysis. The original text used a descriptive language, derived from ALGOL, to present algorithms, and expected students to code them up in either PL/I or Fortran. Students were expected to know a particular language syntax, as well as any peculiarities in either the standard or the compiler available, and to be able to fill in many of the middle steps in arriving at a particular algorithm. The original edition went through many substantially unchanged printings. This 1984 text does just what the title promises; changes the pseudocode to Pascal. Unfortunately, it does nothing else. Computer science has matured in these past ten years, to include much more emphasis on both abstraction and on software engineering. The authors, who publish prolifically, have made no efforts to update the new edition, or even to correct program errors. However, many of those now teaching data structures will have studied from the earlier edition, and will feel comfortable with this text. The original is undoubtedly the benchmark from which more recent books have been written. Kruse Of all five, this book would win the “most liked by students” award. The author believes in “progressing from the concrete to the abstract,” and presents extensive examples of program development. Data structures are introduced to solve particular problems and to improve the runtime performance of earlier programs. Thus, Kruse motivates an abstract data type from a particular application, reversing the currently advocated pedagogy. Algorithmic analysis is addressed, but only in so far as it can be achieved by the techniques of high school algebra. I found myself eager to keep reading and assume students would do so also. There are many programming projects, from revising or completing procedures presented to group projects. Kruse agrees with the inclusion of software engineering techniques and practice early in one's student career. Although it includes work well beyond that proposed in the new CS2 syllabus, it is a viable candidate for use as the primary text for CS2. Then why didn't I choose it for my students__?__ It kept sitting there on my desk in the candidate pile week after week. Although it is an excellent book, per se, it will probably not become a standard for CS2. It is not mathematical enough for students who have already taken a course in discrete mathematics, and it reverses the trend in the undergraduate computer science curriculum to be more like the “real” sciences in establishing a theory first, from which applications flow. None the less, I relegated it to the supplementary shelf with regret. Reingold and Hansen Reingold and Hansen have revised their 1983 text [6] to be Pascal-based, rather than language independent. As such, it becomes much more accessible to lower division students, who are not yet programming experts; that is, if their primary programming language is Pascal. (Is the Modula-2 edition to follow__?__) This book is, to my mind, a true data structures text. It uniformly follows a technique of stating clearly and succinctly what the abstract structure in question is, and what its associated operations do. The authors then present examples and Pascal code. When the topic lends itself, excellent diagrams are included. One of the real pleasures in reading this text is its literateness. Remarks and excellently annotated references at the end of each chapter introduce the student to computer science classics and the pioneers in the field. I was particularly pleased to find one problem in the section on trees based on a little known work by Lewis Carroll. Every bit of the Pascal code has been checked for syntactic accuracy. I briefly wondered, on reading the Preface to this edition, why they had not made trial runs as well. Which brings us to the unsuitability of this excellent book for most CS2s. Most of the algorithms are for single procedures, unincorporated into larger programs. Exercises are mostly of the “draw a diagram,” “design an algorithm to do [some small task],” “modify [some small algorithm] to . . . ,” or “what is the effect of [a few lines of code]” variety. Most CS2 students need to be writing increasingly larger programs that work. However, for a two-quarter or two-semester course in data and file structures, or for students who are either competent programmers or becoming competent in another course, Reingold and Hansen is the best of the five books under consideration here. Tenenbaum and Augenstein This text is widely used in colleges and even in some high schools. It presents numerous algorithms and the data structures necessary to implement them, and is organized for a course in which weekly programming assignments are expected. It is not really a very good book, either in style or in approach (as has been noted by previous reviewers), but does lend itself to a hands-on type course. It suffers from some of the same problems of Horowitz and Sahni, in that it was “translated” from a book using PL/I, and pays little heed to superior features of Pascal. If one were choosing a text for a CS2 course, this would be one of the few now available that would do, in that it covers all the topics at the level of a second semester freshman. The original reviewer did not consider the book a worthy addition to his library, much less the primary text for a course. And yet, one still sees it sticking from the book bags of multitudes of young undergraduates. The second edition is a substantial improvement over the first. Its increased size, from 545 to 774 pages, is due in part to a larger type size, which makes for easier reading. There are also new features. A good description and notation for abstract data types is presented in the introductory chapter, but it is used only to introduce stacks and queues. Nothing has been removed from the first edition, but material has been added on priority queues, general search and B-trees, dynamic hashing, graph traversals, and spanning forests. A new, 73-page Chapter 10 discusses storage management, including garbage collection. The chapter on trees has been largely rewritten, to good advantage, and the graph material moved appropriately from Chapter 7 to Chapter 9. Those who liked the old text will welcome this second edition, but it is not different enough to convert the disaffected. Tremblay and Sorenson This book would be a valuable resource in any student's library. It is, literally, encyclopedic. It includes a great deal of advanced material, such as formal grammars, the basic features of LISP, and an introduction to database systems. An instructor could not cover it all in two semesters, and leaving out some of the early material produces a rather disjointed course. One of the real strengths of the text is the linking of specific hardware implementations to the data structure under consideration. This, of course, flies in the face of an emphasis on abstraction, but for those looking for an engineering (in contrast to the possibly misnamed software engineering) approach, Tremblay and Sorenson offer a lot. A section on algorithmic analysis has been added to the introductory chapter, and subsequent algorithms are analyzed. The authors assume the readers are familiar with combinatorial mathematics, including recurrence relations, but state that such sections can be omitted. Extreme care has been lavished on excellent diagrams throughout. The text includes a long Chapter 7, on file processing. For this, the authors switch from Pascal to PL/I, to take advantage of its superior file handling features. It would be suitable for a two-semester course in data structures and file processing, at the sophomore level, but would be problematic for a one-semester course on either topic. Tables 1 and 2 summarize numerical and qualitative information about the five texts considered.

Reviewer: Doris C. Appleby

Tremblay and Sorenson literally cover all topics recommended for CS2, 5 and 7 [1], and IS2 [2]. This volume is a thorough revision of the first edition, which already has been reviewed [ 18, 5 (May 1977), Rev. 31,289, and 18, 10 (October 1977), Rev. 32,015]. The text is suitable for a two-semester or three-quarter course in data structures and file processing, containing students who are comfortable with PASCAL and have taken, or are concurrently studying, discrete mathematics. It would be especially good in a combined CS/IS program, where both groups have some courses in common. Some students, however, might find the presentation of algorithms in a mixture of pseudo-PASCAL/PL/I conducive to trivial coding errors; e.g., many algorithms include both square brackets (PASCAL), Call (PL/I), and Return (PL/I) statements. Complete programs, when listed, are in (usually) correct PASCAL. (An error was noticed in program “grade” (p. 162). As written, it will never advance past the first line of data.) A reasonable course organization might be to treat the topics of CS5 and 7 in one two-semester or three-quarter sequence, with data structures and algorithms (Chapter 1-6) programmed in PASCAL, and File Structures (Chapter 7, 216 pp.) in PL/I. Algorithmic analysis has been added to the introductory chapter, including the “big O” notation. More detailed analysis of individual algorithms has been added throughout the book. The authors assume that readers are familiar with combinatorial mathematics, including recurrence relations, but state that such sections may be omitted. This assumption is consistent with recommendations that discrete mathematics be a freshman course for both computer science and mathematics majors [4]. As in most revisions, some inconsistencies remain, such as the assertion on p. 12 that the statement, I :2Wn 3/4, will assign a value of 0 to the integer variable I, which is, of course, not only untrue but illegal in PASCAL. The style of writing algorithms has been greatly improved over that in the first edition, with usually one statement per line. The section on number conversions has been deleted from Chapter 1; hardware information has been updated to include storage data for a sample of eight computers. Chapter 2, on character strings, has been reorganized with the bit string example (unimplementable in PASCAL) eliminated. This reviewer finds it odd that array types chosen to represent strings were not packed, as this is the principle use of packing in PASCAL. Chapter 3 contains a new section (3-3) on structures and arrays of structures. Chapter 5, Nonlinear Data Structures, has been rewritten and expanded. Sections on tree traversals are treated in much greater detail than in the first edition. An algorithm for copying a binary tree is developed in full, rather than assigned to the exercises. A new section on the sequential representation of trees has also been added. An extensive example on symbol table construction includes yet another of the authors' superb diagrams. A minor complaint of this reviewer is exemplified by the occurrence on p. 385 of the assumption of variable length strings, with no reference to how this can be managed in PASCAL. Section 5-4, which previously included only Warshall's Algorithm and a modification for finding the length of shortest paths, now includes breadth- and depth-first searches and an algorithm for finding a minimum spanning tree. The Traveling Salesman Problem (the only NP-Hard example) is included here. An instructor wishing to introduce NP problems, as suggested in the CS7 description, might wish to supplement this text with other readings (e.g., [3]). Chapter 6 contains new material on weight-balanced binary trees, 2-3 trees, and tries. Section 6-2.4, on hashing, has been rewritten to great advantage. The old section was entirely too terse for the lower-division undergraduates being addressed. Finally, the lengthy Chapter 7, on files, has been expanded to include external sorting and searching. Algorithms are in PL/I, to take advantage of its superior file handling capabilities. The new sections are clearly written and contain excellent diagrams tracing the various algorithms. Exercises have been revised, program formats modernized, and the bibliography updated systematically throughout the text. The result is an up-to-date textbook containing a wealth of materials. The authors chose to remedy only four of the ten complaints registered by the second previous reviewer. Two of these inclusions may represent differences of opinion, but it is unfortunate that the four trivial misstatements were not corrected.