This book covers classical data structures and algorithms. The traditional material is expanded to improve the student's:
Background. The book has been developed over a period of years and thoroughly classroom tested. The examples expand on the old standards and include many new ones developed (and tested) for this book. It also includes several hundred exercises ranging from straightforward calculation to those requiring the student to expand and generalize the material in the text.
Language. While this is a data structures book, it uses the Ada language. Data structures and Ada have a natural affinity for one another. Ada was the first language to combine information hiding, object modules, generic modules, and error handling, among other software engineering concepts, in an industrial strength programming language. The resulting data structure modules in Ada often have an elegant simplicity missing in other languages.
Audience. This book is suitable for an advanced data structures (CS7) course or an algorithm design course. It assumes the student has a background equivalent to a CS2 course in Ada.
Data abstraction and algorithm design are the basis of modern programming. The book starts with a collection of abstract data types (ADTs). Each ADT is either a data structure itself or an object/class whose implementation illustrates various properties of data structures. The usual ADTs, such as stacks, queues, trees, and graphs, are included along with some others, such as pipes, sets, and sets of sets, which are widely used in practice but seldom included in textbooks.
Presentation of ADTs. Each ADT is presented first in overview form along with pseudocode algorithms designed to emphasize understanding. The language we use determines our concepts, our way of thinking, and our whole approach to a problem. The basic representation of an ADT in terms of, say, an array or a linked list is conceptually independent of any particular programming language. An actual programming language also tends to obscure the concepts under a layer of language specific details. Hence the first presentation of each data structure and its algorithms is in terms of a pseudocode.
A time and/or space discussion and comparison either accompanies each implementation or is included in a summary form at the end of the pseudocode presentation. This is followed by various applications of the ADT.
Ada Implementations. As a general rule there are several possible Ada implementations of each possible ADT design. Ada possibilities include choices
Background Assumed. This is a data structures book and not an Ada book. It assumes the student knows the "Pascal subset" of Ada and presents only those advanced Ada features necessary for good design and implementation. Each new, advanced Ada feature is presented and discussed at the point where it is needed. Thus, the earlier Ada packages are preceded by and include a presentation and discussion of any new or uncommon Ada features.
Although the book assumes the student's background includes the equivalent of the CS2 course, the first few chapters and the beginning of most of the remaining chapters are a review of material normally covered in the CS2 course. This allows the instructor to "fill in" any gaps in the student's background.
Current texts. The currently available data structure books which use Ada are rehashes of Pascal books with the Pascal code replaced by Ada code. Ada is an industrial strength language and these books never expose the student to the real advantages and proper use of Ada. Worse, these texts miss the whole point of Ada, the first language designed to incorporate software engineering principles. This data structures textbook is designed "from the ground up" as an Ada book. All algorithms are designed with software engineering principles in mind and all Ada code conforms as much as possible for an undergraduate text to software engineering principles given in the Ada Quality and Style Manual.
1. Introduction: Basic concepts and a review of background material. (Not included here.)
2. Ada Structures: A review of the basic Ada techniques for representing and manipulating data.
3. Stacks: Stacks with emphasis upon their representation, algorithms, application and coding. Applications include postfix evaluation and conversion of infix to postfix. Ada features discussed include implementing objects along with generics, exceptions, and using subprograms as parameters..
4. Queues and Pipes: Queues and pipes with emphasis upon their representation, algorithms, and applications. Ada features discussed include implementing object classes using generics and initialization.
5. Sets and Bags: Sets and bags along with their representation, algorithms and applications. Besides the usual array and linked representation, this chapter includes the bit-mapped representation and a discussion of the differences between unordered and ordered arrays and linked list implementations. Ada features presented include using functions and procedures as generic parameters.
6. Combining ADTs. Hierarchies of classes and hierarchies of ADTs. Run time declaration of ADTs is presented using a set of sets. Ada features include tagged types and run time declaration of sets, bags, etc.
7. Trees: Trees and their representations, algorithms and applications. A detailed presentation of binary trees, binary search trees, threaded trees, and n-way trees. Applications include using trees to implement bags, expression trees, and priority queues.
8. Graphs: Representations of graphs. Recursive and non-recursive breadth first and depth first traversals. Weighted graphs, minimal paths, spanning trees, and topological sorting. Also includes a discussion of complexity theory along with NP-Completeness.
9. Searching: The interplay between data structures and algorithms and their effect on system speed is illustrated using searching of a simple set. Data structures covered include unordered and ordered arrays and linked lists, trees (both top-down and bottom-up), and hashed arrays. Self-organizing data structures are also introduced. A discussion of the uses of indices is also included.
10. Sorting: Another problem area used to illustrate the effects of data structures and algorithms on system performance and characteristics.
New visits