IMEJ Article - Designing an Algorithm Animation System to Support Instructional Tasks

1.	Introduction
2.	Examining Instructional Tasks
3.	Task Analysis
4.	SKA Design Overview
5.	Authoring
6.	Future Work
7.	References

Printer friendly version

Designing an Algorithm Animation System to Support Instructional Tasks
Ashley George Hamilton-Taylor, University of Georgia
Eileen Kraemer, University of Georgia

Abstract
Existing algorithm animation systems typically have been designed without formal study of related teaching practices. We believe that this has contributed to low adoption rates of these systems. We are conducting a study of instructors teaching data structure and algorithm topics, with a focus on the use of diagrams and tracing. The results of this study are being used to inform the design of SKA, the Support Kit for Animation. We describe a preliminary version of SKA, and possible usage scenarios.

1. Introduction
Over the past decade and a half, a number of algorithm animation systems such as POLKA [12], Zeus [2] and CAT [3] have been implemented. Despite their impressive technical features, studies of their effectiveness have generally produced mixed results [4,9], though a few studies have shown positive results [6]. Moreover, algorithm animation systems are far from being a standard part of teaching practice for relevant courses.

We believe that the appropriate starting point in the design of an algorithm animation system is to examine the tasks instructors perform and the context of these tasks. We have therefore adopted a contextual design [1] approach, in which the first step is to study the user’s existing tasks and workflow. Design proposals are made with the objective of improving the existing system, while a careful attempt is made not to displace aspects of the existing workflow process that enable the tasks to be accomplished. We believe that this design methodology will result in algorithm animation teaching tools that are far more relevant to the needs of both instructors and students. In a similar vein, Hundhausen has conducted ethnographic studies of how students construct algorithm animations, and used the results in the design of SALSA and ALVIS [7].

Another issue that impacts the use of algorithm animation systems is the time it takes to author an animation. The average instructor lacks the free time to create algorithm animations. Some systems, for example Samba [11], have attempted to address this issue, but it appears to be largely unresolved. In one study, Hundhausen found that students took an average of 33 hours to produce a Samba animation [7]. One must write code to create, display, and modify data structures such as graphs and trees in all but a few systems such as JAWAA [10] and Object-TRAKLA [8]. We have attempted to minimize authoring time by providing an extensible library of visual data structure objects, and a set of simple operations that facilitate access to these objects.

2. Examining Instructional Tasks
In order to inform the design of SKA, we are conducting an ongoing study of computer science instructors conducting algorithms and data structures classes. We are particularly interested in identifying the types of data structure diagrams used, and classifying how they are used. This study is being conducted over a number of semesters so that we can observe a number of instructors. So far, two instructors have participated. We have identified a set of topics that will eventually include the most commonly taught algorithms and data structures. The relevant classes are videotaped, and we subsequently ask students to allow us to photocopy their class notes so we can see what they have captured and compare it to the videotaped material.

Our present approach to videotape analysis is to divide topics (e.g., binary search trees) into subtopics (e.g. binary search tree insertion), and divide the subtopics into segments - for example, an introductory discussion, examples, further discussion, and analysis. We identify the tasks performed in each segment and the time spent on each task, noting any use of diagrams. We also record the use of annotations and gestures used in conjunction with the diagrams. An example of this is the following summary of the binary search tree deletion video session:

About the authors...

Duration (min)	Activity
Part 1
1:00	Introduces topic.
0:30	Copies tree diagram.
0:30	Annotates tree diagram with keys to be deleted, traces leaf deletion.
1:00	Traces key deletion, constructs two possible resulting trees.
1:00	Discusses general rule for deleting interior nodes.
2:30	Traces key deletion, circles successor/predecessor nodes, writes notes on them, draws resulting trees. (All the traces above were done using diagrams only)
Part 2
6:30	Writes deletion algorithm, describing fragments along the way. Annotates one algorithm fragment with explanation.
1:00	Continues writing algorithm, referring to tree diagram to explain what a certain fragment does.
1:00	Refers to diagram to show what the fragment about to be written will do. (Both references are gestures along path of tree that the algorithm fragment will follow).
0:30	Copies tree diagram.
2:00	Traces key deletion using algorithm. Annotates tree diagram with pointer variables from algorithm (Diagram becomes somewhat cluttered with arrow annotations).
3:00	Starts redoing example because of errors encountered. Needs to get rid of arrows, so erases and recopies tree diagram. Draws added arrows more carefully, traces very carefully, going back and forth between diagram and algorithm.

Thus far, we have observed data structure diagrams being used in (a) tracing algorithms, sometimes without a written algorithm, (b) discussing or describing properties of the data structures or algorithms, and (c) deriving or confirming theoretical analysis of algorithms. These findings are summarized in Table 1.

Topic	Diagram			Diagram Usage
	Type	tracing	analysis	discussion	drawing	gestures	annotations
Binary Search, part 1	Array	algorithm and diagram	none	yes	construct array	point to statements of algorithm	index vars for array in trace
Binary Search, part 2	Search tree	algorithm and diagram	yes	yes	construct tree	point to tree properties, path, nodes
Interpolation Search	Array	algorithm and diagram	yes	yes	copy array	point to array area accessed	index vars for array in trace
Binary Search Tree Insertion	Tree	algorithm and diagram	none	yes	copy tree, update tree	point to tree path, nodes	add, cross out pointer variables during trace
Binary Search Tree Deletion, part 1	Tree	diagram only	none	yes	copy tree, update tree		mark subtrees. Add, cross out pointer variables
Binary Search Tree Deletion, part 2	Tree	algorithm and diagram	none	yes	copy tree, update tree	show path, affected nodes before writing algorithm	Add, cross out pointers. Add arrows to show path followed
2-3 Tree Deletion	Tree	diagram only	none	yes	construct tree, update tree	indicate direction of rotation

Table 1. A summary of task types for each subtopic.

We have found that data structure diagrams can be abstract, concrete, or both. An abstract diagram typically contains no data and is often a compact representation of a data structure. An example of this is the use of a triangle to represent a tree. A concrete representation shows all of the important data, for example all the key values in the data structure diagram. Some diagrams are part concrete and part abstract, for example, a concrete tree with an abstract subtree.

As shown in Table 1, we have also observed a number of types of annotations and gestures. For example, annotations are used to track variable values during tracing and highlight sections of data structures while gestures are used to identify elements that are being accessed or compared, and to indicate properties such as the number of elements, path followed, etc., for an entire data structure diagram or part thereof.

We recorded the time spent doing various types of tasks, as summarized in Table 2. The time spent using diagrams (tracing or joint use) varied considerably over the topics observed thus far, but in almost every case it is a substantial portion of total time spent. Note that the percentages add up to more than 100% unless joint time is excluded, because joint time is time spent on more than one task (one of which involves diagrams).

Topic Time

trace

analysis

discussion

joint

total (min)

Binary Search, part 1
80%

0%

20%

0%

5.0

Binary Search, part 2
16%

24%

7%

49%

30.5

Interpolation Search
47%

0%

29%

0%

24.5

Binary Search Tree Insertion
25%

0%

75%

19%

8.0

Binary Search Tree Deletion, part 1
62%

0%

31%

0%

6.5

Binary Search Tree Deletion, part 2
49%

0%

51%

14%

17.5

2-3 Tree Deletion
59%

0%

41%

27%

11.0

Table 2. Percentage of time spent on each type of task.

We are still in the process of analyzing the students' notes. All we can say at this time is that some students decide to take sparse notes, or none at all, preferring to try to observe the lecture, while others try to take detailed notes but often fail to capture the many changes made to the diagrams and algorithm traces.

3. Task Analysis
An examination of the tasks the instructors perform while discussing algorithms and data structures in a lecture in the absence of an algorithm animation system allowed us to identify some tasks that could be supported by a system. We found that diagram use is an integral part of the discussion process. In general, we observed that more than half the time spent on a topic involves the use of data structure diagrams (DSD's). In particular, we found that:

DSD's are used primarily for tracing tasks, but also for analysis and general discussion.
DSD construction, manipulation and tracing using DSD's are often performed in the absence of a written algorithm.
Tracing is performed in a flexible manner, which varies from doing a single operation to showing the effect of a segment of an algorithm.
DSD's often have to be copied to perform a new trace or record a history of DSD states.
Annotations are used in a variety of ways. For example, they are used to record changes, show a path or series of accesses in DSD's, and to relate steps in the algorithm to actions on DSD's.
Gestures are used to connect spatially separated entities, give an intuitive indication of direction or size, etc. For example, a gesture can be used to show the direction of a search in a DSD.

We have chosen to support these diagram construction, manipulation, and tracing tasks because we have observed that they are tedious, time consuming and error-prone. The preliminary version of SKA, the Support Kit for Animation, is an initial attempt to do so.

4. SKA Design Overview
SKA is a combination of a visual data structure library, a visual data structure diagram manipulation environment, and an algorithm animation system. SKA has a library of a visual data structure classes. New visual data structure classes can be added by library developers, as we will discuss in the next section. When the SKA environment is started, instances of a visual data structure (an interactive data structure diagram) can be created and manipulated on the canvas (seen in the upper part of Figure 1), independent of any algorithm.

Manipulations include adding and removing elements, highlighting parts of the visual data structure, and performing other operations specific to that data structure class, such as deleting a subtree in a tree data structure.

A Powerpoint file showing how an AVL tree is manipulated to show the effect of rebalancing.

A visual data structure may be cloned (copied), and the clone can be manipulated independently. Each visual data structure instance has a corresponding model data structure instance. Cloning creates a separate copy of the visual/model data structure pair, but with identical elements and configuration.

A visual data structure may also be saved to a file and read in later. However, this preliminary version of SKA does not handle the abstract data structure diagrams referred to in the instructor study.

Powerpoint file showing how a graph is cloned by the user.

Figure 1. An algorithm below is waiting for the user to select a directed graph from the canvas on the left.

The SKA environment can execute animated algorithms. The authoring process will be described in the next section. When invoked via a menu, a pseudocode algorithm appears in an execution panel, seen in the lower part of Figure 1. Through this panel, the user may run the algorithm, pause and resume, set and remove breakpoints before or during execution, or step through the algorithm a line at a time. The user can also reset (terminate) an algorithm and run it again.

An algorithm can use, as input, a visual data structure on the canvas created by the user. This same visual data structure is also manipulated by the algorithm. Algorithms can also create visual data structure instances on the canvas. An algorithm can even request the selection of an element from a particular visual data structure instance. During a pause or break, a user may make clones of a data structure that is being used by (bound to a variable of) an algorithm, and manipulate either the clones or the original. Such a manipulation of the original might cause an error in the algorithm, but this can be used to illustrate erroneous states.

Multiple algorithms can be run in parallel, even multiple instances of the same algorithm. However, the comparative execution time of these algorithms is often meaningless because of the varying time each algorithm spends pausing, waiting on input, and performing animation.

A Powerpoint file showing how a breadth-first search algorithm is run, using a graph from the canvas as input.

5. Authoring
How does an instructor prepare an animated pseudocode algorithm in SKA? We start with the source code for the algorithm (henceforth called the code), seen in the upper part of Figure 2.

Figure 2. The original algorithm source code is on the left. The annotated code is below, in which the Graph g is replaced with a SkaGraph, and showAlgLine() calls are added to connect the pseudocode lines with corresponding source code. Extra setSelected(true) calls are added to highlight visited vertices.

The present implementation language is Java because of its widespread use in computer science education, and its support for user interface development. The first step in preparing an algorithm visualization is to replace the data structures we wish to display with equivalent SKA data structures, seen in the lower part of Figure 2. Next, the instructor writes a pseudocode equivalent of the code. The level of detail or style of the pseudocode does not matter, since the pseudocode is merely displayed, not executed. We annotate the source code by placing showAlgLine() calls to mark which line of pseudocode corresponds to which line of code. If we want to get a data structure from the canvas, we replace the input routines with a canvas inputVizDS() call. Any extra animation calls (e.g. to highlight some element) are then added. The code is then compiled with the relevant SKA libraries.

Developing a new visual data structure class is more difficult, though we have attempted to provide a framework that simplifies their development, particularly for user interface operations. We expect to provide enough data structure classes to fulfill the most common needs, with more classes coming on stream over time.

6. Future Work
We expect to complete our instructor study by the end of the academic year, and we will be redesigning aspects of SKA based on our findings. For example, we are aware that support is needed for annotations, and ideally this should be pen-based. A simple animation action library is also being developed for SKA, based on perceptual principles [13].

We believe that SKA will be useful in lectures as well as one-on-one tutorials, group discussions, and self-study. User studies are being planned to see if this is indeed the case, and an initial version of SKA will be made available when this phase is complete. We believe that SKA will allow instructors to better utilize time both in preparation and in the classroom, and that that our research represents a radical re-examination of algorithm animation system design, beyond that called for by some in the field [5].

7. References
[1] Hugh Beyer and Karen Holtzblatt. Contextual Design: Defining Customer-Centered Systems. Morgan Kaufmann (1998).

[2] Marc Brown. ZEUS: A system for algorithm animation and multi-view editing. Proceedings of the 1991 IEEE Symposium on Visual Languages, pages 4-9, Kobe, Japan, October 1991.

[3] Marc H. Brown and Marc A Najork. Collaborative Active Textbooks: A Web-Based Algorithm Animation System for an Electronic Classroom. Proceedings of the 1996 IEEE Symposium on Visual Languages, pages 266-275, Boulder, CO, September 1996.

[4] Michael D. Byrne, Richard Catarambone, and John T. Stasko. Evaluating animations as student aids in learning computer algorithms. Computers & Education, Vol.33, No.5, pp.253-278, 1999.

[5] Judith S. Gurka and Wayne Citrin. Testing effectiveness of algorithm animation. Proceedings of the 1996 IEEE Symposium on Visual Languages, pages 182-189, Boulder, CO, September 1996.

[6] Colleen Kehoe, John Stasko, and Ashley Taylor. Rethinking the evaluation of algorithm animations as learning aids: An observational study. International Journal of Human-Computer Studies, Vol.54, No.2, pp.265-284, February 2001.

[7] Christopher Hundhausen. Toward Effective Algorithm Visualization Artifacts: Designing for Participation and Communication in an Undergraduate Algorithms Course. Unpublished Doctoral Dissertation (Tech Rep. No. CIS-TR-99-07), Dept. of Computer and Information Science, University of Oregon, 1999.

[8] Korhonen, Ari. Algorithm Animation and Simulation. Unpublished Ph.D. thesis (2000), Helsinki University of Technology.

[9] Andrea W. Lawrence, Albert M. Badre, and John T. Stasko. Empirically Evaluating the use of Animations to Teach Algorithms. Proceedings of the 1994 IEEE Symposium on Visual Languages, October 1994, pp. 48-54.

[10] W. Pierson and S. H. Rodger. Web-based Animation of Data Structures Using JAWAA, Twenty-ninth SIGCSE Technical Symposium on Computer Science Education, 1998, pp. 267-271.

[11] John Stasko. Using Student-Built Algorithm Animations as Learning Aids. Technical Report GIT-GVU-96-19, Georgia Institute of Technology, August 1996.

[12] John Stasko and Eileen Kraemer. A Methodology for Building Application-Specific Visualizations of Parallel Programs. Journal of Parallel and Distributed Computing, Vol.18, No.2, June 1993, pp.258-264.

[13] Colin Ware. Information Visualization: Design for Perception. Academic Press (1999).

********** End of Document **********


IMEJ multimedia team member assigned to this paper	Yue-Ling Wong