An Object-Oriented, Apprenticeship Approach to Data Structures using Simulation

(This work is supported in part by the National Science Foundation Grant #DUE-9554910 )
Owen Astrachan Trevor Selby Josh Unger
(This paper appears in the proceedings of FIE '96, Frontiers in Education)


Object-oriented methods and programming are increasingly being used in the second (CS 2) data structures course in Computer Science. As this course migrates to an object-oriented approach, students and instructors must be given materials to support a unified and application-oriented course. In this paper we report on modules developed for what we term an Applied Apprenticeship Approach to the CS 2 course using an object-oriented framework.

Our philosophy is that CS 2 students learn best as apprentices, by studying the work of more experienced program designers and writers and by extending and modifying programs provided by these experienced programmers. In our Applied Apprenticeship Approach (AAA) project, we use applications to study data structures, rather than studying data structures to use in applications. By inverting the traditional method of study [11], we hope to engage students from the outset by providing practical and illuminating examples for how and why data structures are used. In this paper we report on two modules developed to support an apprentice style of learning (see, e.g., [2, 4, 10, 11]). Materials supporting this style of learning, including the modules described here, are accessible via the web; the URL is Each module supplies code libraries and frameworks, explanatory material for students and instructors, and potential programming, lab, and homework exercises. Each module supplies a situated learning experience [9] that engages students from the outset by providing a practical and illuminating example for how and why data structures are used. Each module is a simulation. The first simulates a virtual world inhabited by creatures with different behavior. The second module is based on queuing simulations, and, in particular, on designing and implementing control for multiple elevators in a building [14, 17]. The classes used in each module integrate several data structures into a real-world program, providing both text and graphical displays of the simulation. Each module has been developed to support object-oriented (using C++) design and programs, but will be developed as an Abstract Data Type (using C) to reach as wide an audience as possible.

The primary goal of the Applied Apprenticeship Approach (AAA) project is to support introductory Computer Science courses with assignments, teaching materials, and a software component library that can be used by students of all abilities. These materials will be useful in any college or university, without requiring a change in philosophy, a re-organization of courses, or a profound investment in new equipment.


Currently all module animations are done using either Samba or its Java equivalent Lambada. Samba was developed by John Stasko [15] but runs only under X-windows. (Samba (and Polka under which it runs) are accessible via the web As part of the AAA project, we have developed a Java version of Samba called Lambada. Lambada runs all Samba program and provides additional features not available in Samba. Both Samba and Lambada receive commands via pipes; the commands are plain text which students find quite easy to develop.


Situated learning [9,12] engages students in the learning process. Simulation provides a context for situated learning and is well-suited to object-oriented techniques. Several references include material on developing class hierarchies for simulations [1, 4, 6], but this material requires extensive elaboration by instructors to develop assignments that can be used across several semesters. We have found that the time invested in developing large programming assignments makes one-time use impractical. The modules discussed here permit assignments to re-used in different ways providing similar, but not identical, problems. This prevents (to some degree) students from copying work done by others in previous semesters.

In the next two sections we describe the two modules including supporting tools and materials we have developed for generating graphical animations.

Darwin: Artificial Life

\section{Darwin: Artificial Life} The first simulation is akin to an artificial life [13] simulation. The module is called Darwin and is based on an assignment given in the Stanford University Computer Science Department. Creatures inhabit the squares of the grid-based Darwin world as shown below. The program simulates the behavior of the creatures.


Each creature belongs to a different species which determines the creature's behavior. Behavior is dictated by a program (written in DULL: Darwin Unstructured Lattice Language). For example, the Flytrap species program is shown below. Flytraps do not move, but infect creatures in front of them. Flytraps spin when no creatures can be infected.

ifenemy 4 left go 1 infect go 1 Other DULL commands include right, hop ifwall, ifsame, ifempty, and ifrandom.

In a simulation, each creature gets a turn. During a turn, a creature executes part of its program in which it can see directly in front of itself and take an action depending on what's there. Infecting a creature turns it into the same species doing the infecting. The ultimate goal is to be the fittest creature and survive by taking over the world. When a turn ends, another creature gets a turn. When every creature has had a turn the process begins again with each creature getting another turn. This continues indefinitely until there is only one species left or until some predetermined time limit is reached.

Seven classes are used to implement the Darwin program. Data structures used include one- and two-dimensional arrays. Pointers are used to link creatures to the world they inhabit. In the current implementation, a creature points to the species to which it belongs; species programs are initialized when the program begins. Alternatively, creatures could be implemented using inheritance although this could make it more difficult to change species when infection occurs.

We envision several uses of the Darwin simulation as the basis for assignments. Students can be asked to implement any subset of the classes (except, perhaps, for the graphics class). The behavior of the world can be modified to be toroidal rather than flat. Students can write an assembler for DULL (programming in DULL is a particularly dull experience, our web pages include the code for a DULL assembler written in Perl.) Finally, experience at Stanford indicates that students enjoy design competitions. In the case of Darwin students are asked to design a species that will do best at dominating and taking over the world. Instructors can coordinate an automated round-robin tournament to determine which species is the best. Instructions and experiences for holding such a contest will be included in our web-based materials.

Discrete Event Simulation

Several books have small case studies using event-driven simulations [8, 16]. However, these projects do not employ inheritance and are not written to encompass the large-scale programs we would like students to use as part of the AAA project. Discrete event simulations provide a good example of event-driven programming: essential for understanding the behavior of simulations, but used more generally in many object-oriented systems, such as client-server based concurrent systems and graphical user interface (GUI) frameworks.

We have developed two simulations: a relatively simple multiple server, single queue/multi queue simulation of a bank or fast-food restaurant and a more elaborate simulation of a multi-story building with many elevators. The bank simulation will serve as an introduction to discrete event simulation and a lead-in to the more complex elevator simulation. Alternatively, the simulation can be a stand-alone lab or programming assignment depending on how much students are asked to design and code.

The classes and class-hierarchies used in the simulations are more complex than is typically found in textbooks. However, the classes are designed to scale-up to large simulations and to emphasize current state-of-the-art object-oriented methods. In particular, the simulation module described here uses design patterns described in [5] for iterator classes and for observer classes. An elementary use of an observer class in the context of a random-walk simulation, but suitable for beginning students can be found in [3]

Observer Patterns

TThe observer pattern (also called publish-subscribe based on the model-view-controller paradigm from Smalltalk) is used to separate data with how the data is observed. In our use, a graphical observer shows an animated view of a discrete event simulation while a file observer records the history of the simulation as a sequence of textual event descriptions. Observers inherit a common interface from an abstract base class. Because each object in the simulation notify all its observers, it is possible to have several observers at once. This facilitates a graphical display that is more fun to watch and is useful for on-line debugging and a textual representation of the simulation useful for post-mortem debugging.

Banking Simulation

The snapshot of the banking simulation below shows a four-server, single queue simulation. The customer second from the left (named Deborah Goldfarb) is leaving, there are 15 customers in the queue, and the global time is 1602 simulated seconds. This snapshot is from a screen dump using the Samba animator (see Animations).


Customers in the banking simulation have the same behavior although each has a service time based on either a uniform or negative exponential distribution (time can also be read from a file to facilitate replaying a simulation.) The data structures used includes queues, priority queues, and arrays/vectors. We envision the banking simulation used to introduce the concept of simulation without requiring students to implement queues, for example. However, instructors may choose to bypass the elevator simulation because of the complexity of the class hierarchy.

Elevator Simulation

The simulation of several elevators in a building provides a rich context for exploring issues in data structures, queuing theory, and object-oriented design and programming. Knuth [7] provides a lengthy description of an elevator simulation focusing on physical properties of the elevators including acceleration between floors and the time for doors to open and close. Our module makes simplifying assumptions about elevator behavior to focus more on program and class design in addition to elevator control. A snapshot of a ten story, two elevator simulation is shown below.


Students can experiment by designing and implementing elevator control algorithms. For example, idle elevators might remain at the last floor visited, return to the bottom floor, or cruise between floors. Students will also design and implement customers with different behaviors (here a customer is an elevator-user). A simple class hierarchy for customers is shown below. An object of the Hacker class takes the elevator to a floor, codes for 15 hours, and then leaves the building. In contrast, a pizza person makes four inter-floor deliveries remaining on each floor for only the few minutes that it takes to deliver a pizza. These changes are made by implementing the function CreateEvent() differently for each subclass of Person.



Our modules provide instructors with a wide range of programming and lab exercises. Assignments can be simple, e.g., implement one member function of one class or complex, e.g., implement a heap-based priority queue and all the classes that control elevator behavior. Modules include code and assignments enabling instructors to re-use concepts as well as code for several semesters. The assignments are application oriented and enable students to work with large programs without implementing the program from scratch. Where possible, assignments have a graphical component using a platform-independent animation package. These modules will be tested during the 1996-97 academic year and updated based on feedback from those using the assignments. The modules described in this paper, and several others, are all accessible via the world-wide web.


  1. Harold Abelson and Gerald Jay Sussman. Structure and Interpretion of Computer Programs. MIT Press, McGraw Hill Book Company, 1985.

  2. O. Astrachan and D. Reed. AAA and CS-1: The applied apprenticeship approach to CS 1. In The Papers of the Twenty-Sixth SIGCSE Technical Symposium on Computer Science Education, pages 1--5. ACM Press, March 1995. SIGCSE Bulletin V. 27 N 1.

  3. Owen Astrachan. A Computer Science Tapestry: Exploring Computer Science and Programming with C++. McGraw-Hill, 1996.

  4. Owen Astrachan and Claire Bono. Using simulation in an objects-early approach to cs1 and cs2. In OOPSLA: Object Oriented Programming Systems, Languages, and Applications: Educator's Symposium, pages 1--8, October 1994. Portland, Oregon.

  5. Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

  6. Adele Goldberg and David Robson. SMALLTALK-80: The Language. Addison-Wesley, 1989.

  7. Donald E. Knuth. The Art of Computer Programming, volume 1 Fundamental Algorithms. Addison-Wesley, 2 edition, 1973.

  8. Robert Kruse, Clovis Tondo, and Bruce Leung. Data Structures and Program Design in C. Prentice-Hall, 2 edition, 1997.

  9. Glenn Meter and Philip Miller. Engaging students and teaching modern concepts: Literate, situated, object-oriented programming. In The Papers of the Twenty-Fifth SIGCSE Technical Symposium on Computer Science Education, pages 329--333. ACM Press, March 1994. SIGCSE Bulletin V. 26 N 1.

  10. Bertrand Meyer. Object-Oriented Software Construction. Prentice-Hall, 1988.

  11. Bertrand Meyer. Toward an object-oriented curriculum. Journal of Object Oriented Programming, pages 76--81, May 1993.

  12. Richard Pattis. Get A-Life: Advice for the Beginning C++ Object-Oriented Programmer. Turing TarPit Press, 1997.

  13. Mitchell Resnick. Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds. MIT Press, 1994.

  14. Marja-Liisa Siikonen. Elevator traffic simulation. Simulation, 61(4):257--267, October 1993.

  15. John Stasko, Albert Badre, and Clayton Lewis. Do algorithm animations assist learning? an empirical study and analysis. In INTERCHI 93 Conference Proceedings: Human Factors in Computing Systems, pages 61--66. ACM Press, April 1993.

  16. Mark Allen Weiss. Algorithms, Data Structures, and Problem Solving With C++. Addison Wesley, 1996.

  17. Edward Yourdon and Carl Argila. Case Studies in Object-Oriented Analysis and Design. Prentice-Hall/Yourdon Press, 1996.