| Owen Astrachan | Trevor Selby | Josh Unger |
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 http://www.cs.duke.edu/~ola/apprentice.html. 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 http://www.cc.gatech.edu/gvu/softviz/parviz/samba.html.) 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.
In the next two sections we describe the two modules including supporting tools and materials we have developed for generating graphical animations.
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.
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.
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]
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.
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.
