Complex programs rely on a variety of class and object relationships. Beginning students can only begin to approach these levels of complexity in their programs. Focusing on a few class relationships in sequence can provide a foundation for object-oriented design, while giving students a taste of design methods for larger programs.
In Spring 1995, our department decided to switch from using Pascal as its main teaching language to using C++. As part of this decision, it was felt that a complete switch to the object-oriented paradigm would be more beneficial, rather than using C++ as ``a better C'' in the introductory courses and later introducing classes and objects. This implies that an early introduction to object-oriented design is necessary.
During the summer of 1995, a colleague and I wrote a new syllabus for our introductory course and developed class materials. These were tested in the fall of 1995, revised, and again tested in spring 1996. Our second course was similarly overhauled in fall of 1995, tested in spring 1996, and is currently undergoing revisions. Both courses will again use the new materials in fall and spring of the coming academic year.
In both courses, I have tried, with mixed success, to incorporate design topics into the standard C++ curriculum . Current textbooks do not address object-oriented design or address it either late or inadequately. My goal for the workshop is to gain new ideas for teaching design in introductory courses.
In addition to teaching the first two courses, I have taught a stand-alone object-oriented programming course based on C++ to juniors and seniors several times over the past few years. I have also incorporated object methodology into both undergraduate and graduate software engineering courses. I have attended several object-oriented design workshops at past SIGCSE conferences.
Introductory computer science students are often overwhelmed by learning a programming language and development environment, yet underwhelmed by simple programming assignments. This is aggravated by covering the necessary language syntax needed for the next courses, which often leaves little time to discuss design issues. While this is true both of procedural and object-oriented approaches, the object paradigm may suffer more because of it. Postponing the discussion of design fails to make good use of the inherent power of the object-oriented method.
In order to integrate class and object design into the introductory curriculum, a sequence of design problems is proposed. These problems are to a large extent language-independent, but they are intended to lead to implementations in C++. The sequence relies on several common class and object relationships, described below. These relationships are not original; they are standard material from object-oriented design textbooks.
The relationships chosen are simple enough that they can be implemented in an introductory course. While more complex relationships can be discussed without implementation, students need the feeling of accomplishment gained from programming actual solutions. In addition, a sound foundation of class design provides the basis for later design topics.
The first relationship in the proposed sequence is class containership, the part-whole relationship. After gaining experience with simple classes that have member data, this relationship should be a natural extension, since the class that plays the role of ``part'' is also member data. Nested class structures allow students to build more significant structures using simple components.
The second relationship is aggregation. This follows naturally from using arrays. It is also an extension of the part-whole relationship. Aggregation is used to collect a set of objects from a common class. Since arrays are not the only kind of aggregate collection, this can lead to discussions of other types of container classes, such as linked lists or dictionaries.
The third relationship is object association. This is achieved by passing one object as a parameter to another object's member function. The parameter type may be value, by reference, or by address, depending on the exact relationship. This relationship is necessary for one object to operate on another object.
The fourth relationship is inheritance. Of the four relationships, this one is handled best by existing textbooks. However, without practice, it is the hardest one for beginning students to understand and use correctly.
As noted above, current introductory textbooks pay no, limited, or very late attention to object design. Most, however, do provide examples that make an inherent use of class design, but without an explicit discussion of class and object relationships. Introductory texts rarely go beyond class data and responsibilities. See, for example,  or . Of course, there has been much written about object-oriented design. However, this has been at a more advanced level. Books such as McGregor and Sykes  discuss object-oriented design from a software engineering viewpoint. Also, Booch  and Shlaer and Mellor  advocate a particular methodology for doing design.
 Adams, Joel, Sanford Leestma and Larry Nyhoff, C++: An Introduction to Computing, Prentice-Hall, 1995.
 Barrett, Martin L., ``Emphasizing Design in CS1'', 27th SIGCSE Technical Symposium, 1996, pp. 315-318.
 Booch, Grady, Object-Oriented Analysis and Design, Benjamin/Cummings, 1994.
 Decker, Rick, and Stuart Hirshfield, The Object Concept, PWS Publishing, 1996.
 McGregor, John, and David Sykes, Object-Oriented Software Development, Van Nostrand Reinhold, 1992.
 Shlaer, Sally, and Stephen Mellor, Object-Oriented Systems Analysis, Prentice-Hall, 1988.