Data Structures and Software Development in an Object Oriented Domain

Using a unique parallel-coverage approach that is designed to fit the varied backgrounds of advanced first-year or second-year students, this text 1) introduces aspects from all phases of object-oriented software engineering using UML (analysis, architectural and detailed design, implementation and testing), and 2) presents some of the more formal aspects of data structures, and their design, use, implementation, and analysis. Content is thus equally accessible to students with a moderate background in both data structures and object-oriented programming or to those with only background in one or the other—i.e., students easily absorb software engineering material while working with concrete techniques and data structures, or vice versa. The text uses Eiffel as the implementation language, and features two case studies that illustrate the steps followed in an object-oriented development process for the analysis and design of non-trivial systems.

Key features

• Unique integration of data structures, library design, and software principles into one package. Designed to help students absorb software engineering material while working with concrete techniques and data structures. Presents data structures and software engineering concepts in parallel by intermixing individual chapters on data structures and software engineering. Begins with simple software engineering concepts, and repeatedly uses them to develop applications throughout the book.
• As-needed coverage of selected concepts and techniques. E.g., the basics of the language Eiffel are presented in Ch. 2; subsequent chapters add various constructs. as they are needed for specific purposes. The same approach is used for timing analysis, and UML notation.
• Two case studies. Illustrates the steps followed in an object-oriented development process for the analysis and design of non-trivial systems (a simple banking system and a student registration system). Explains the selection of the most appropriate data structure. Solutions are given in the Solutions Manual.
• Use of Eiffel as the implementation language. Uses only moderate amounts of code. An extensive reference for the Eiffel language is included in an appendix.
  • Eiffels clean and simple syntax allow more advanced concepts, like exceptions, to be studied without cluttering the simple concepts.
• A simplified methodology for system development. Uses a subset of the UML to present the results of analysis and modeling; makes extensive use of diagrams using the UML to portray key aspects of the system design and software relationships (e.g., inheritance, context, sequence, class, high-level architecture, and subsystem); and uses the methodology to develop significant applications that use the data structures being developed in parallel. Focuses on software design issues and patterns related to producing loosely-coupled, cohesive systems.
  • Presents basic software engineering concepts at a level accessible to advanced first-year or second-year students.
• A judicious use of the UML graphical notation.
  • Gives visual representations of artifacts produced during the software development process (static and dynamic structure).
• Standard data structures. Developed, analyzed, applied, and placed in an extensive data structures library (e.g., lists, stacks, queues, trees, balanced trees, graphs, and files). all presented along with their ADTs, appropriate applications, implementations and time and space analyses. Most of these data structures have iterators for traversing the data structures, and the library also has a number.
• Abstract Data Types. Presented from both the constructive and the axiomatic approaches using an object-oriented notation.
• Extensive coverage of timing analysis. E.g., the analysis of recursive algorithms (first by counting the number of calls and second by recurrence relations).
• A full chapter on software testing. Deals with traditional black-box and white-box test case generation techniques as well as testing techniques for object-oriented software. Provides special emphasis on how to deal with ADTs and inheritance.
• Unique coverage of the modeling of the problem domain. To obtain a problem domains static and dynamic structure. Models the static structure using types of relationships such as inheritance, aggregation and associations; models the dynamic structure with events, users (and actors), use cases, and object interaction diagrams.
• Software contracting with assertions. (Preconditions, postconditions, class invariants, loop invariants and loop variants) to deal with correctness and robustness.
• Review of basic mathematics. For handling summations, logarithms, and functions (in an appendix).
• An extensive collection of problems and projects (case studies). At section-ends and chapter-ends. Exercises deal with programming, analysis and design, testing, timing/space analysis of algorithms, algorithms to manipulate various data structures, using mathematical induction to prove properties of certain data structures such as trees. Solutions are included in the Solutions Manual.
  • Offers an abundance of hands-on practice with basic concepts and challenging opportunities to apply them.
• An accompanying CD. With all code for the text, the data structures library, an Eiffel compiler and associated environment.

• 1. State of Software Development.
• 2. Eiffel Basics.
• 3. Objects and Classes.
• 4. Arrays and Algorithm Analysis.
• 5. Abstract Data Types and Their Implementation.
• 6. Lists.
• 7. Dispensers: Stacks, Queues and Priority Queues.
• 8. Object-Oriented Development: An Example.
• 9. Trees.
• 10. Elementary Problem Modeling and System Design.
• 11. Principles of Software Design.
• 12. Software Testing.
• 13. Bags, Sets, and Dictionaries.
• 14. Sorting.
• 15. Graphs.
• 16. Files.
• Appendix A: Eiffel Tutorial Reference.
• Appendix B: Math Primer.