ALGANI - ALGORITHM ANIMATIONS For COMPUTATIONS

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

1 Introduction

In an algorithm animation environment, 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. Such an environment makes use of the concept of a script (typically used as high-level macros) to allow interactiveness. This project started with the implementation of an animator for specific algorithms (ALGANI 1). This system was later revamped to become a generic algorithm animator (ALGANI 2). The scope of a generic algorithm animator is very wide; thus to reduce the scope, only a few basic requirements were selected to design and implement ALGANI 2.

2 A specific animator: ALGANI 1

In the first phase of this project a teaching tool was developed that could animate some commonly used algorithms such as sorting, graph and BST algorithms. These algorithms were hard-coded into the program. To enable the user to have a better understanding of the algorithms, the display and animation were made unique to each algorithm.

3 A generic animator: ALGANI 2

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. To realize ALGANI 2, two important components were identified: a graphical editor and an animator.

3.1 Graphical Editor

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 within the drawing window were implemented to enhance 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.

3.2 Animator

The animator allows the user to compile an algorithm and to activate an animation. Using this animator it is possible to animate an 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. Lastly, these algorithms can be ported into the animation environment. This is accomplished through the following steps:

  1. Open a pipe to allow ALGANI 2 to issue shell commands.
  2. Compile the algorithm source code with the animator library and report possible errors.
  3. Execute the compiled program while listening for requests.
  4. The executable file sends animation commands to ALGANI 2 through the pipe.
  5. ALGANI 2 decodes the commands and performs the animation accordingly.

After implementing the BST insertion algorithm into ALGANI 2 it was concluded, that the quality of animation using ALGANI 2 is only slightly inferior to ALGANI 1, the source code is shorter, and the time spent for implementing the animation using ALGANI 2 is much shorter.

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.