There is a growing recognition in academic circles that computer science is a laboratory science. It seems that the data abstraction course, particularly, lends itself well to this kind of treatment. A laboratory component can provide an innovative learning environment, helping to convey an understanding of the classical abstract data types in a more concrete realm. In order to illustrate fully the importance of the various phases of the uniform design methodology derived from the notion of an abstract data type, from abstraction to implementation, it is argued that students need to participate in laboratory experimentation and to communicate the results of their findings in formal reports, much like those we associate with the more traditional sciences of chemistry, physics, or engineering. We have found, however, that these objectives are realistic only if the instructor makes a corresponding reduction in the responsibilities for the more traditional homework problem assignments.
The data abstraction course can be approached through a uniform methodology consisting of three separate and distinct design phases -- abstraction, implementation, and application -- relative to the notion of an abstract data type (ADT). Abstract data types, as explicit programming language structures, have only begun to appear in a few languages of more recent vintage, e.g., in the class construct of C++ or the package in the language ADA. However, we have the opinion that the notion of an abstract data type is an indispensable conceptual design tool, regardless of the language being employed.
In our treatment of ADTs, we will usually introduce (abstract) operations, axioms, and one or more mathematical models (wherein the operations are given a concrete interpretation) for which the axioms are seen to be satisfied. All in all, this is a study of syntax, semantics, and realization in a pure mathematical setting, one that provides an intuitive insight for the subsequent implementation, and for applications relating to a particular ADT. Thus, in the case of the stack ADT, one proposes the abstract operations:
with respect to an underlying elementtype X. The pair of axioms: provides the meaning (semantics) of the operationsIn the mathematical model in which stacks are interpreted as finite sequences S = < x1, x2, ... , xn-1, xn> from X, the concrete operations:
are seen to satisfy the axiomatic system, and moreover, they provide the key to a proper implementation of the stack ADT.
A further consideration of the intended applications, however, suggests the inclusion of two more abstract operations, a zero-ary (i.e., constant) CREATE operation, for initializing a stack as empty, and a unary ISEMPTY operation, for testing a stack for emptiness. These in turn necessitate the inclusion of additional axioms, beyond the two listed above (we leave the student the task of supplying these additional axioms, e.g., what should be the result of attempting to access the top of an empty stack?).
The full implementation phase of the study is then approached with a specific programming language in mind, e.g., the C++ language. One would propose any number of distinct implementations for stack, as an array structure, as a pointer-based structure, etc., all modularized as a C++ class. Most often, a close examination of the abstraction phase of the study will suggest an implementation. We then compare and contrast the various implementations from the standpoint of their computational complexity, ease of programming, clarity of design, etc., to arrive at a best alternative.
Finally, in the applications of an ADT to a particular problem area, it is hoped that the data types that are to be utilized have been so designed (in reference to the available operations) that the applications programmer has little to do but to call the various ADT class operations in a client program, as if these operations had been primitive to the programming language, when in fact, they have been well-chosen to provide an extension to the language at a higher linguistic level. To the largest degree possible, the client programs are designed so as to be independent of the implementation; it thus creates a separation of levels of abstraction that is crucial to a successful and effective program design effort. Altogether then, we have a well-organized methodology for treating the complete problem-solving design task, from abstraction to implementation, to applications.
The laboratory activity can take place outside of class, informally, perhaps organized by the student participants themselves (a so-called open laboratory). Or, as some academics have favored, it can take place in a specific laboratory setting, at specific times, under supervision (a closed laboratory), granting however that it is generally necessary for the experiment to be completed and its results reported elsewhere. It is understood that each student will write a formal laboratory report on the findings of each experiment that he or she performs. The style of these reports should conform to that outlined in the Guide for Laboratory Reports.
Most instructors will agree that it is all right for students to confer (particularly those who are members of a laboratory team, assuming that the class has been so organized), for this is an important part of the learning experience. Nevertheless, each student should be expected to do his or her own problem solving and analysis and write an individual laboratory report. In the case where the programming tasks have been partitioned among members of a team, the author of each program unit should be clearly identified.
Most importantly, the style of all C++ programs should conform to that developed in class and in the text(s). This is particularly crucial, and it must be uniform, as regards the naming of the various C++ class operations: uppercase for the abstract operations, e.g., PUSH, lowercase for the interpretations, e.g., push, and "mixed" in the case of the class functions, e.g., Push. In fact, all such "naming" conventions must be employed uniformly throughout the course, and throughout the various experiments. The style of the programs in the main text -- Cerrano, Helman, and Veroff, Data Abstraction and Problem Solving in C++, Addison Wesley, 1998, particularly as regards the naming of class constituents, must be viewed as an absolute and rigorous "template" in this regard.
Each student will submit solutions to the individual laboratory quizzes at the beginning of each laboratory period. These quizzes consist of routine questions relating to the descriptions of the experiments, together with the accompanying reading assignments (listed as references to the experiment descriptions) and relevant lectures.
We have chosen as the subject matter for our experiments, the following topics:
Each of these experiments is described in full in the handouts the student receives a few days prior to the beginning of a laboratory period.In consulting the experiment descriptions, the student will see that he or she is asked questions that are equally balanced between theoretical and experimental issues, some of which require rather extensive C++ programming, while others are more in the nature of a traditional homework problem assignment. Note however, that these questions appear in the form of exercises. And yet, we would insist that in the writing of laboratory reports, these exercises do not appear in an explicitly numbered fashion at all, but rather, their solutions are woven into a coherent treatment of the topic at hand. The fundamental distinction in comparing our laboratory work units with the usual homework assignment is the cohesion and the depth of study that is involved in preparing a laboratory report that provides an adequate summary of the area of investigation.
In this respect, we encourage the student to give free reign to imagination and creativity, to exercise his or her own best judgment in choosing from among the many questions he or she is asked to consider (adding original topics of particular interest, as well), so as to actively participate in the design of the experiment. This point of view is gaining credibility for the modern engineering school approach to laboratory work and for the broader goals of academic pursuit, more generally. And certainly it is in keeping with the spirit of experimentation that we intend to foster in the present context.