Last updated at 4:21 pm UTC on 14 January 2006
An Algorithm Animation Exploration System
Ashley George Taylor
CS8503 Fall ’98, Prof. Stasko
Algorithms are complex, and many students find that an algorithms or data structures course is one of the most challenging in the Computer Science curriculum. The complexity of algorithms has led researchers and instructors to seek ways of presenting algorithms visually. One reason they are complex is because even basic algorithms are often based on non-intuitive strategies. Algorithms are also dynamic, changing state while carrying out operations.
Algorithm Presentation Challenges
Traditionally, instructors have taught algorithms using a combination of verbal and textual descriptions, pseudocode, and examples. The goal is to show how and why the algorithm works, relate it to a strategy, prove its correctness and analyze its efficiency. The examples are typically done by giving an overview of the strategy employed, then stating each main operation while performing it and/or referring to pseudocode steps prior to changing the data representation of the algorithms’ state on the board. If the algorithm works on a diagrammatic data structure such as a tree, the data representation is usually a diagram. The diagram is sometimes shown in conjunction with the representation of the data structure, e.g. an array, and other pertinent state variables.
The advantage of doing examples this way is that students can usually see what the instructor is doing, i.e. what about the state is being changed, because one can follow the instructors physical movements. The combination of gestures, movements, and verbal emphasis can be very effective if skillfully done.
The disadvantage is that a complex example can take all or most of a class period. It is difficult for instructors to go over earlier states or to present different scenarios because of the time involved. The point of the example is often lost because many students miss some step and lose track of what is happening. Students often think they will catch on as they go along and are too embarrassed to interrupt the instructor, who by then has probably erased the state for the step they missed because the board can hold only so much. Note-taking allows students to annotate the example and go over it later, but often causes them to miss something the instructor said or did. It is also difficult to capture individual states of the algorithm if the instructor is just changing previous values (which is common) - capturing the state would mean copying the entire board while the instructor makes a few changes. If the basic algorithm is misunderstood, students may miss the underlying strategy and the analysis. This is particularly likely for students who build their conceptual structures on concrete examples.
At present, the defacto use of algorithm animations is for demonstrations, either in lectures or for individual review. Many animations are roughly equivalent to typical manual lecture examples, but some animations introduce a visual metaphor, e.g. sticks for data values to be sorted. Animations are hardly user-tested for clarity. Many animations have a ‘runaway horse’ feel which makes it difficult for students to track operations and difficult for the instructor to effectively control execution to demonstrate salient features. We believe that students often miss points in animations because the pace was too fast or because too many things were happening simultaneously or in close temporal proximity [’97 focus group sessions]. Even when speed controls are used, some operations can be too slow while others are too fast, diminishing the perceptual advantage of smooth motion. The critical operations are often glossed over because they happen at the same or faster rate, though they require special attention [I really want to do a formal study on this before someone else does]. Despite all this, students report that some animations are very useful, both in lectures and for individual use. Some students say they need to run an animation at their personally preferred pace to follow it [focus group]. However, many of the issues mentioned previously remain.
In general, the lack of planned content and user testing limits the usefulness of algorithm animations. Applying improved multimedia design and user-testing methods has been shown to result in software which can improve learning outcomes significantly [Mayer, Faraday]. We believe that applying proper design methods can result in provably useful animations, and that improved animation tools can facilitate the design and deployment processes.
Proposed System Usage
We believe that algorithm animation can facilitate the efficient demonstration of examples in lectures, while giving instructors most of the freedom they had manually to manipulate the state of the algorithm at any time, and relieving them of the burden of drawing complex diagrams and manually executing complex algorithms. We propose to design an animation system which is flexible enough to use in various teaching situations, some of which we probably have not thought of. The goal of this system is to give instructors precise control over the execution of an animation by adding the advantage of recording, recalling, copying, modifying, or replaying the state of an algorithm at specified intervals. We want to save examples so students can replay and explore them, to free students from detailed note-taking. We also want to allow instructors to manipulate diagrams or metaphoric representations and have the changes reflected in the internal data. Instructors will also be able to change the internal data directly.
For example, an instructor could use an animation in a lecture on quicksort as follows:
1. Describe the context of the invention and/or use of the algorithm.
2. Introduce the high-level strategy using a high level animation in which the instructor picks (clicks on) a pivot value, then shows the array with all smaller elements on the left, larger on the right (how they got there is ignored for now). The array is then split, and the instructor points out or guides students to conclude that if we keep doing this recursively on each part of the array, then recombine, this sorts the array.
3. Discuss partitioning using an animation. During the left-to-right phase the instructor puts in a breakpoint which freezes the animation during each comparison of the element to the pivot, and asks students if the target element has been found. During the right-to-left phase the instructor puts in a pause so the animation does a brief delay during each comparison, and a breakpoint so it stops at the target element.
4. After the swap, the instructor clones the display/state and asks students to predict the next swap elements, and moves the left and right pointers accordingly. The original display/state is run, and the result is discussed if it differs from the prediction. Further predictions can be made without cloning - if we move the pointers on the original display/state, the pointers jump back to their former positions when animation execution resumes.
5. Just after the last swap, discuss partition termination. Ask for predictions on the meeting/crossing point. Discuss divide and show it step-by-step. Show next partition with predictions if time allows. Run through rest of animation at faster pace, but slow enough for students to track actions, and pause just before each split.
After discussing and showing bubble sort on a ‘normal’ data set, an instructor could also modify data to point out inefficiencies by looking at special cases, e.g.:
1. Change the last (largest) element to be smaller than the first element. Run the animation on this new data.
2. Change the first element to be larger than the last element. Run the animation again.
3. Change an arbitrary element to be larger than the last element. Run the animation again.
This shows that a sorted list with the first element out of place takes k passes to sort if it belongs in the kth place. This could be done by using separate data sets, but if a student asks the instructor to make a change, it is easier to modify the display instead of changing an input file.
An instructor could also modify a graphical data structure such as a tree, e.g. in an animation in which a new element is inserted in an AVL tree:
1. After an element has been added to the tree which causes an imbalance, the instructor asks students to predict what happens.
2. For each prediction, the instructor clones the animation, and moves subtrees using a selection tool. Any missing links can be drawn using a line tool.
3. The original animation is run and compared to the predictions.
This would be very time-consuming to do manually.
Engagement is also a goal for individual use. The system would allow authors to fork clones at selected points and ask students to make predictions. We would also include audio support so narration and audio annotation can accompany animations. Narration has been shown to be effective in certain situations because it relieves the student from reading detailed text while watching animations [Faraday and Sutcliffe] and provides synchronous information [Mayer]. We expect that an animation designed for individual use will require more cues than one designed for a lecture because we must attempt to fill in for instructors gestures, etc.
Comparison to Existing System Paradigms
The system will have three aspects to it: a programmable graphics/animation library, and an object editor, and an execution control environment. The object editor will be somewhat akin to an object drawing program. However, certain changes will affect data values, making the system closer to a model-based drawing/design program or visual simulation environment.
Computer-based drawing tools can be thought of as encompassing a spectrum of capabilities:
- Painting programs simply paint bits. Groups of bits have no identity. Any arbitrary area can be changed, but the most such a program will do is remember the last change(s). The model is based on actions upon bits.
- Object-drawing programs define each entity produced by a drawing tool as an object. Objects can be selected, moved, copied, and otherwise manipulated. They can be combined into group objects. The model is that of user actions on graphical objects.
- Design drawing programs such as CAD programs attach attributes to graphical objects which can be manipulated numerically or visually. Attributes may have user-defined constraints.
- Graphical modeling/design environments extend CAD capabilities by connecting graphical objects to models. Models may be defined algebraically or may be simulations. Object attributes may be model inputs or outputs, or both. Depending on the constraints, changes may be made graphically, numerically or via the model.
The system also bears some relation to certain programming environments:
· Some visual debuggers permit modification of the data structures, but do not support user-friendly rendering of complex data structures or user-defined data visualizations.
· Visual simulation environments are similar to the graphical modeling/design environments, but are geared towards simulation construction rather than precise drawing. They support graphical manipulation of the output, but have limited animation or execution control capabilities.
The proposed system would have the following capabilities:
1. Animation Architecture
- Script-based animation language to facilitate simple animation construction and controlled state manipulation
- User-defined actions can be added to language
- Object control of actions per unit time, rather than frame-based control
2. Object Manipulation and Editing
- Selection, movement, and other manipulation of single objects or groups, including diagrams, graphical entities and data structures
- Editing of data structure values
- Manipulation of entities changes internal data, where defined by the user
3. Execution Controls
- Reversible execution, perhaps limited to defined points, based on invisible clones or history/change log
- Interactive specification of break points, so instructors can control stopping points and remove them as needed
- Speed control for individual actions to control pace of execution
4. Cloning - allow an animation to be cloned to facilitate:
- Visual comparison to later state
- Manipulation the state to predict future states
- Modification and execution to show difference in execution from original state
5. Environment Enhancements
- Fades and reveals for text and objects to direct users’ attention
- Audio annotation to provide narration and explore use of audio cues
Unlike previous systems, this system is predicated on live objects which can be manipulated and edited. A frame-based system such as Polka [Stasko] is based on an output paradigm, which makes it difficult to have live objects. We believe that animation based on a time-step will allow better interactive control because it synchronizes rendering and user-interaction.
The initial prototype will concentrate on providing basic animation per clock unit, simple graphical manipulation capabilities, and cloning.