Data Structures and Software Development in an Object Oriented Domain, Eiffel Edition (Object and Component Technology Series) [Hardcover]

Jean-Paul Tremblay (Author), Grant A. Cheston (Author)

Book Description

Publication Date: March 8, 2001 | ISBN-10: 0137879466 | ISBN-13: 978-0137879465 | Edition: Eiffel ed

For CS2/CS7 Data Structures courses. Also appropriate for first- and second-year Object Oriented Design courses where instructors also want to re-enforce data structures from an object-oriented perspective. Using a unique parallel-coverage approach, this text 1) presents the fundamentals of data structures from arrays and lists to balanced trees, graphs, and files (including their design, use, implementation, and analysis); and 2) gives an introduction to object-oriented software engineering using UML (including the context diagram, use cases, sequence diagrams, architectural and detailed design, implementation, and testing). It can be used (a) to mostly present data structures with little software engineering, (b) to present both topics in parallel, or (c) to review data structures from an object-oriented perspective and then concentrate on software engineering at the first or second year level. The text uses Eiffel as the implementation language, an object-oriented language particularly well-suited to the clean presentation of data structures and software engineering concepts.Two case studies are included to illustrate the steps followed in an object-oriented development process for the analysis and design of non-trivial systems.

Editorial Reviews

From the Back Cover

FEATURES

• Use of a subset of the UML—Shows how to use UML for analysis and modeling.
• CD-ROM included—CD contains an Eiffel compiler and development environment, all the code for the text, and the data structures library.
• Modeling of the Problem Domain—Absent in other texts, this book models the problem domain that an object-oriented project must begin with.
• Two case studies—Illustrates the steps followed in an object-oriented development process for the analysis and design of non-trivial systems.
• Extensive Data Structures Library—Consists of the standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files.
• Extensive Reference for the Eiffel language—A full-featured object-oriented language, Eiffel, specifically developed for large object-oriented systems.

Excerpt. © Reprinted by permission. All rights reserved.

Preface

Most computer-science curricula have at least one course in data structures. Such a course s usually taken by all majors, since its contents are used in subsequent courses. Historically, his course has dealt almost solely with data structures, including their time and space analyses (along the lines of the courses CSl and CS2 of the ACM88 Curriculum). However, in recent years such a course is also expected to give students a good object-oriented programming background, and, increasingly, an introductory background in software development. This is in keeping with the ACM/IEEE-CS Computing Curricula 1991 report, which emphasizes, among other things, software engineering and software design, rather than merely implementing the data structures in an object-oriented language.

Whereas this book is designed for our present second-year course taken by all our majors, it is also appropriate for the second term of first year (i.e., CS2) in some situations. In particular, it will be useful to those institutions that have a strong object-oriented CS1 course and wish to present more on application-level software development to their students. To fit at the CS2 level, the book includes all the material on the basic data structures arrays and linked lists-before treating more advanced data structures. The amount of the advanced material that can be covered in a second-term first-year course will depend on the background of the students and the pace of the course. However, the book has more material than can typically be covered in a CS2 course. As a result, it can also be used in a subsequent course to develop more depth in data structures and software engineering. Alternately, if first year uses a breadth-first approach, this book will be suitable for a strong second-year course that integrates data structures and software engineering.

Our presentation is from an object-oriented perspective and includes many of the recent software engineering techniques for an object-oriented development of a system. For our implementation language, we have chosen Eiffel, a language specifically designed for developing large object-oriented systems. It is a full-featured object-oriented language that includes abstract classes, assertions such as preconditions, postconditions, and class invariants, multiple inheritance, generic classes, exception handling, automatic garbage collection, and GUI interfaces. In particular, preconditions and postconditions were designed to support the software engineering approach of Design by Contract. Also, the simple concepts can be expressed in a clean and simple syntax without being clouded by a multitude of alternatives, options, and exception handling. Even for more complex concepts, the syntax is still simple, although the semantics necessarily increase in complexity. Although Eiffel is the language of implementation, we only use moderate amounts of code.

Like in most other recent data structure books, abstract data types (ADTs) are discussed early. ADTs offer several advantages that include encapsulation and information hiding. In any object-oriented programming language, a deferred/abstract class provides a clean implementation of an abstract data type. Also, the use of inheritance facilitates the design of modular, extendible, and reusable systems. The existence of multiple and repeated inheritance in Eiffel opens up more possibilities for the system design implementation.

But using ADTs and inheritance in developing software does not by themselves guarantee quality software. One of the primary goals is to integrate several software-engineering principles with the data structures content of the course. Students at the first- or second-year level should be introduced to the principles of software engineering, but they do not have the programming experience to understand the problems or complexities of writing large projects. Often, if these software principles are studied in isolation, they can be beyond their comprehension and are viewed as just requiring more work. They do see the need for data structures, and, with a library of data structures, they can design and build much larger applications. Thus, the book integrates data structures, library design, and the software principles into one package. Obviously at the first- or second-year level, software engineering cannot be presented to the depth of a third-year or fourth-year/graduate course. However, by gradually introducing more and more software design concepts when building up a data structures library, students can obtain a surprisingly good background in the analysis and design of software systems.

However, our discussion of software development is not limited to the data structures library context. We begin with simple software engineering concepts and repeatedly use them to develop applications throughout the book. After students have developed a working knowledge of the software basics, the more advanced concepts are introduced throughout the remainder of the book. The students absorb the software engineering material while working with concrete techniques and data structures.

An important part of this book not found in most other texts is the modeling of the problem domain. Any nontrivial object-oriented project must begin with problem modeling, and even at the first- or second-year level, students need exposure to modeling concepts. The static structure is modeled using types of relationships such as inheritance, aggregation, and association. The dynamic structure is modeled with events, users (and actors), use cases, and object-interaction diagrams. We develop and present a simplified methodology for system development. Included with it is the use of appropriate diagrams using the Unified Modeling Language (UML) to portray the key aspects of the system design. We use the methodology to develop significant applications that use the data structures being developed in parallel.

Some important aspects of this book are:

• The presentation of basic software engineering concepts at a level suitable for advanced first- or second-year students, including the use of a subset of the UML to present the results of analysis and modeling. Also, there is extensive use of diagrams to portray software relationships, which includes using the following types of diagrams: inheritance, context, sequence, collaboration, class, high-level architecture, and subsystem.
• The' standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files, are developed, analyzed, applied, and placed in an extensive data structures library. Most of these data structures have iterators for traversing the data structures. The library also has a number of implementations of keyed and non-keyed dictionaries.
• The discussion of software engineering includes the concepts of Design by Contract, cohesion, and coupling.
• The object-oriented techniques of inheritance and polymorphism are used. Single inheritance is introduced in Chapter 2 and frequently used thereafter. Multiple inheritance is presented in Chapter 6 and used to define many of the data structures of the library. Polymorphism is introduced in Chapter 6 and used in both the data structures library and applications.
• Two case studies illustrate the steps followed in an object-oriented development process for the analysis and design of nontrivial systems.
• Timing analysis is extensively studied and used throughout. This includes the analysis of recursive algorithms, first by counting the number of calls and then by recurrence relations.
• A full chapter is included on software testing, which deals with traditional black box and white box test-case generation techniques, as well as testing techniques for object-oriented software.
• Abstract Data Types are presented from both the constructive and the axiomatic approaches using an object-oriented notation.
• Eiffel, the language used for implementation, is a full-featured object-oriented language. It has automatic garbage collection, polymorphism, multiple inheritance, generic classes, assertions for the support of the Design-by-Contract approach, and exception raising and handling. Eiffel was designed with a clean and simple syntax so that more advanced concepts, like exceptions, don't clutter the simple concepts.
• An extensive reference for the Eiffel language is included in an appendix.
• Some of the concepts and techniques are introduced on an as-needed basis rather than overwhelming the student with a full treatment of the topic in a single chapter. For example, the basics of the language Eiffel are presented in Chapter 2, and most of the subsequent chapters add various constructs, as they are needed for specific purposes. This approach is also used for timing analysis and UML notation.
• An appendix reviews basic mathematics for handling summations, logarithms, and functions.
• An extensive collection of problems is included. Also, there are a number of case studies that are suitable for student projects.
• A CD is included with the book that contains all code for the text, the data structures library, and an Eiffel compiler with its associated environment.

Summary by Chapters

Chapter 1 examines the phases present in most software development processes. This chapter explores briefly factors that are important in assessing the quality of software systems. The chapter also examines some fundamental principles of software design that have been used in the production of quality software. It concludes with an overview of three approaches to software design.

Chapter 2 presents the basics of the Eiffel language. The main goal of this chapter is to cover Eiffel's elementary constructs so that a student can write simple programs.

Chapter 3 introduces the elements and mechanisms that constitute the object mode...

Product Details

• Hardcover: 1071 pages
• Publisher: Prentice Hall; Eiffel ed edition (March 8, 2001)
• Language: English
• ISBN-10: 0137879466
• ISBN-13: 978-0137879465
• Product Dimensions: 10.1 x 8 x 2 inches
• Shipping Weight: 4 pounds
• Average Customer Review: 2.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #3,119,682 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

5 of 5 people found the following review helpful:

4.0 out of 5 stars As a student, December 13, 2001

By 

"tenzig_shirpa" (Saskatoon, Canada) - See all my reviews

This review is from: Data Structures and Software Development in an Object Oriented Domain, Eiffel Edition (Object and Component Technology Series) (Hardcover)

I had the pleasure of being one of the test audiences for this particular book. I'm basing my review on my copy, 1,000+ pages of photocopied draft. I was introduced to it via a full-year course taught by Dr. Temblay and Dr. Cheston.

The book is basically about a couple things: Writing superior Data Types via OO processes and an introdution to OO developement.

The section on datatypes is very good. The datatypes are constructed using string OO processes (the cd contains all the code for the datatypes created in the book) and are a good learning process. There is an emphasis on abstraction and generics in the design which is an intelligent way to do things, and I learned a lot about datatypes and OO through this. The section on formal ADTs, however, I found incomprehensible, but others may have different opinions.

The authors do focus on important OO concepts like UML and use cases, the brief section on software design suggests using the waterfall method. This section is fairly good, and is a decent introduction for a subject that can be fleshed out in further classes. It is still introductory however. For instance, patterns are not heavily mentioned, nor other development practices.

Other ideas focused on were mathematical induction, a strong section on testing, sorting theory and files as well as algorithm timing and reccurence relations.

This is a good book, and most undergrad students could likely learn a lot from it, assuming they are willing to spend a little time learning eiffel.

1 of 2 people found the following review helpful:

1.0 out of 5 stars Wretched book for a wretched class, September 20, 2005

By 

Ao Me Akuma (Canada) - See all my reviews

This review is from: Data Structures and Software Development in an Object Oriented Domain, Eiffel Edition (Object and Component Technology Series) (Hardcover)

I took a full two semesters of Computer Science from the professors who actually wrote this textbook. The course was easily one of the worst I have ever taken in university and I could spend pages detailing how much I hated it, but instead I'll simply talk about the book.

Data Structures and Software Development in an Object Oriented Domain attempts to introduce students to the concepts of Software Engineering, as well as expanding upon the theory and application of various data structures AND all the while explaining the Eiffel programming language, and therein lies the problem. Quite simply, it bites off much more than it can chew. The textbook is massive; over 1000 pages, with the words packed in tight with a teensy-tiny font making it hard to read. Every chapter goes into a ridiculous level of detail that would never be covered in class, even through two semesters. The sheer information density makes for difficult reading, especially when trying to extract the essentials. Some sections border on incomprehensible simply due to the density of the material...so much so that during class, the professor actually photocopied and clarified the material from his own textbook as handouts! The general exposition itself is incredibly dry and unintuitive, and you'll find yourself skipping over pages and pages until you find whatever it is your looking for. I don't think I'm exaggerating when I say that half the material could be thrown away. Clear and concise it ain't.

Compounding this problem is that the chapters are poorly laid out and do not flow logically. Sections as diverse as timing anaylysis, arrays, binary trees, implementation of abstract data types (ADTs), etc. are thrown about willy-nilly. The Data structures bits are mixed in with software engineering bits, making for disjointed reading. As if to acknowledge this problem, near the beginning of the book one finds a nonsensical schematic of each chapter's "prerequisites". Why this was done instead of simply arranging the chapters in a more logical order is beyond me.

Data Structures and Software Development in an Object Oriented Domain is a ridiculously bloated and expensive textbook that I would never recommend, but like most college texts you will have no choice in buying it. Buy it, and then sell it the day classes are over.