Using Animation to Understand Algorithms in a
Multimedia Teaching System

Kai Warendorf, Wen-Jing Hsu, Yew-Chong Chia
School of Applied Science
Nanyang Technological University
Singapore 639798
wdorf@uranus.sas.ntu.ac.sg, hsu@ntuvax.ntu.ac.sg

Abstract

An algorithm animation environment is a means for exploring the dynamic behavior of algorithms that makes a fundamental improvement in the way we understand and think about algorithms. It presents graphical views of an algorithm in action, exposing properties that might otherwise be difficult to understand. In the first phase a user-friendly tool was developed that can animate selected algorithms (ALGANI 1). The second phase involves developing a platform that can animate arbitrary algorithms (ALGANI 2).

Keywords

algorithms, animation, multimedia, teaching.

1 Introduction

In an algorithm animation environment [Brown 1988], the dynamic behavior of algorithms can be explored and uncovered. Through the use of multiple graphical displays, all views are updated simultaneously in real time as the algorithm is executed. New algorithms, graphical displays, and input generators can be implemented and run with existing libraries of these components. This environment makes use of the concept of a script (typically used as high-level macros) to allow interactiveness. An obvious application of an algorithm animation environment is to show static diagrams of algorithms and data structures in a teaching environment. Students can further explore the properties of an algorithm by using their own data with different displays (from a library of existing displays). More advanced students can code their own algorithms and utilize the set of displays available in the system.

An algorithm animation environment can also be used as a tool for research in algorithm design and analysis. Human beings have a limited memory which tends to be inefficient and error prone when processing large amounts of visual information and data. With this tool, interactive experimentation can be performed to produce accurate pictures that best illustrate the desired properties of an algorithm.

Many people have attempted to realize an algorithm animation environment [Brown 1988, Myers 1983, Herot et al. 1982, Baskerville 1985]. In contrast the authors took a different approach to realize such an environment. This project started with the implementation of a specific algorithm animator (ALGANI 1). As the name suggests, ALGANI 1 can only animate a selected number of algorithms. This system was later revamped to become a generic algorithm animator (ALGANI 2).

2 A specific animator: ALGANI 1

The purpose behind the first phase of this project was to develop a teaching tool that could be used for laboratory support in a course on data structures and algorithms. The initial plan was to produce a workable module that could animate some commonly used algorithms such as sorting, graph and tree algorithms. Building a generic library for animating arbitrary algorithms was not the scope of this project since the intention was to use it as a demonstration teaching tool.

2.1 User Interface Design

In designing the user interface, special attention was given to its user-friendliness and the ability for future upgrading. The term user-friendliness means that the user should be able to use the software without much help. The cascading pull-down menu is one way of enhancing the future upgradability of the software. To upgrade the software, new algorithms can easily be included in the pull-down menu. Figure 1 shows the user interface of ALGANI 1.

2.2 How the animation works

Three phases are involved in this animation environment: namely the idle, initialization and animation phases. The system always starts with the idle state. At this point the user can choose between the type of input: interactive or from data file. After the data is retrieved and the initialization phase is completed, the user may select any algorithm from the pull down menu and click the play button for a complete animation or click the step through button for a step-by-step animation (animation phase).

Figure 1

Figure 1 User interface of algani1

2.2.1 Selection sort

To start off, choose the selection sort algorithm from the menu and specify the input type. A bar chart will be displayed in the display window as shown in Figure 1 if data is obtained from a data file. The height of each bar is proportional to its numerical value. To insert any data to the display, the user simply keys in the new value in the item field and clicks the add button. The height of all the bars will be readjusted if necessary. The small bar below the bar chart indicates the number of keys that have already been sorted. Figure 2 shows the selection sort algorithm in the middle of its execution.

2.2.2 Binary Search Tree (BST)

Three operations are implemented on the BST data structure: insertion, deletion and searching. Setting the input mode to user input a set of buttons are displayed in the function window (Figure 3). Using these buttons the user can interactively communicated with the objects in the display window and perform the above operations. Figure 3 shows an example of an insertion. The red edges show the path of traversing to the insertion point.

Figure 2

Figure 2 Sorting animation (Animation phase)

Figure 3

Figure 3 BST insertion


3 A generic animator: ALGANI 2

Upon completion of ALGANI 1, the authors gained insight into how algorithms can be animated. Therefore it was simpler and more efficient to design a software that allows the user to animate arbitrary algorithms. The desirable features that such a system should possess were derived as a result:

Being generic, ALGANI 2 would not be able to animate all algorithms satisfactorily. The quality of the animation would depend very much on the effort put in by the user developing it. So far, the graphical editor implemented is rather primitive and the research is still going on. To realize ALGANI 2, two important components were identified: a graphical editor and an animator.

3.1 Graphical Editor Design

The editor allows users to edit the shapes and sizes of the object they wish to use when animating the algorithm. The features supported were those found in simple graphical editors like clearing the window, zooming in and out, grid on and off, saving and retrieving from a file. Grids were implemented to help the programmer to measure the movement of the animation. Another important feature is the ability to zoom an object in and out. This feature ought to be implemented as a basic part of the software requirement, or else future upgrading will be more difficult. The data structure used for storing objects is illustrated in Figure 4.
Figure 4
Figure 4 Data structure for object type

Every object has an object ID; this ID is used to identify different objects when animating an algorithm. To create an object, first enter the intended object ID in the object ID field. Insertion of an object is done by moving the mouse pointer to a empty grid space and clicking the left mouse button. To delete an object, just click the middle mouse button when the mouse pointer is pointing to the object. To change the color of the subsequent objects that are being drawn, click on the intended color on the color palette. The objects drawn can be saved to a file for future editing.

3.2 Animator Design

The animator consists of buttons for compiling an algorithm file and activating an animation (Figure 6). Using this animator it is possible to animate any algorithm by first creating objects using the graphics editor. Following this, the user can build algorithm files with the standard libraries to define the motion of objects. Figure 8 shows an example of how the algorithm can be coded. Lastly, these algorithms can be ported into the animation environment. This is accomplished through the following steps (Figure 5):

  1. Open a pipe to allow ALGANI 2 to issue shell commands.
  2. Compile the algorithm source code with the animator library.
  3. Execute the compiled program while listening for requests.
  4. Executable file sends animation commands to ALGANI 2 via the pipe.
  5. ALGANI 2 performs the animation accordingly to the commands.

Figure 5

Figure 5 Communication between ALGANI 2 and the algorithm file

Figure 6 shows the result of a simple animation using the following animation algorithm. The algorithm moves the letters [F Y P] which are on the same line and separated by one grid unit together and lowers the middle letter [F Y P]:

MOVE (1, RIGHT);
MOVE (2, DOWN);
MOVE (3, LEFT);

Figure 6

Figure 6 Result of animation

4 Comparison of ALGANI 1 and ALGANI 2

As mentioned earlier, one of the purposes of ALGANI 1 is to facilitate the development of ALGANI 2. After completion of both the systems, their strengths and weaknesses were compared. To do this, the insertion sort and BST insertion algorithm were animated using ALGANI 2. Figure 7 and 8 show the state of the data structures after the animation of these algorithms. The conclusion drawn from these two examples is as follows:

The results obtained were very encouraging because "ease of use" is a very important feature in any software.

Figure 7

Figure 7 Animating insertion sort algorithm with ALGANI 2


Figure 8

Figure 8 Animating BST insertion algorithm with ALGANI 2

ALGANI 2 should only be viewed as the starting phase of an ambitious algorithm animation environment. In order to use it efficiently, the user may need to have some experience in animating algorithms; though, naïve users can still make use of it to create some simple animation.

While creating some animation examples using ALGANI 2, the authors were able to probe into the algorithm design and thus able to determine the exact locations of bugs. In such situations, ALGANI 2 not only met the initial requirement of being a tool for research in algorithm design and analysis, but it can also be used as a debugging tool.

5 Upgrading and Enhancement

ALGANI 1 was build as an animation tool for algorithms. In the present stage the system is only a presentation tool. The input data to the system is variable, but once retrieved, the system basically works on its own without any interaction between user and computer. In order to get a more sophisticated teaching tool the students should be allowed to present their own solution and have it analyzed. In the BST algorithms for example, the students should be able to perform the insertion or deletion of a node themselves. This might enhance the students understanding of the algorithms.

At this stage, ALGANI 2 can only animate some simple algorithms satisfactorily. When the complexity of an algorithm grows, the animation would become more abstract due to the restricted set of animation commands (e.g. MOVE and INSERT) available. This also means that to be able to understand the animation, the user would need to know the symbolic meanings of each objects on the display. Below is a list of factors to be noted before proceeding with the upgrading.

6 Conclusion

ALGANI 1 and 2 should only be viewed as the starting phase of an ambitious algorithm animation environment for both naïve and experienced users. In addition to meeting the initial requirement of being a tool for research in algorithm design and analysis, it can also be used as a debugging tool.

At the present stage of this project, its contributions can be very subtle. But with good software engineering skills, upgrading of this project should not pose any major problems. A lot of low level functions were written to enforce the principle of information hiding. Programmers, who wish to upgrade the system, can use them (if required) with ease and without much knowledge of their implementations. ALGANI 2 is designed in such a way that it provides mechanisms to support many types of animation rather than enforcing any one policy. The concept used is quite similar to the one used in the design of the X Window system. With such a design, new toolkits can be built on top of the present version to provide better animation quality.

References

M.H. Brown (1988), Algorithm Animation, MIT Press

B.A. Myers (1983), "Incense : A System for Displaying Data Structure," Computer Graphics, 17, 3

Schneider, A.I. Wasserman, Eds. (1982), "Automated Tools for Information Systems Design", North Holland Publishing Co.

D.B. Baskerville (1985), "Graphic Presentation of Data Structures in the DBX Debugger," Report No. UCB.CSD 86.260, University of California at Berkeley, Berkeley, CA