The history of algorithm animation development extends to the past two decades. But the earliest algorithm animation evolved can be back traced in 1966, when an animation of link-list language, L[6], was created by Ken Knowlton at the Bell Telephone Laboratories. Major development of algorithm animation starts in the early 80s.
In 1981, a video, Sorting Out Sorting, was created by Ronald Baecker at the University of Toronto. This is generally credited with initiating the field of algorithm animation. Since then, educators have adopted algorithm animation to help teach algorithms. Between 1980s and early 1990s, two seminal systems were evolved, which have significant influences on all others that followed. These systems were BALSA-I (Brown ALgorithm Simulator and Animator) [Brown 1984] and TANGO (Transition-based Animation GeneratiOn) [Stasko 1990].
BALSA-I was the first widely known algorithm animation system. It was developed by Marc Brown and Robert Sedgewick at the Brown University. BALSA-I is an interactive algorithm animation system that supports multiple simultaneous views of an algorithm's data structures and can display multiple algorithms executing simultaneously. Its evolution motivates other researchers to participate in the development of other algorithm animation systems. It also raises a number of issues which can better improve the system that other researchers in the field may have interests in.
Another system, TANGO, was developed by John Stasko who was at Brown University when the system was developed. The emergence of TANGO introduces the path-transition paradigm for animation design and a framework for algorithm animation system. It introduces a new conceptual framework which is adopted by many later systems as their fundamental architecture. This architecture will be described in the next section.
Since BALSA and TANGO have been developed, descendent systems of these two remarkable systems were also developed. BALSA-I has one descendent system, BALSA-II [Brown 1988]. BALSA-II is a domain-independent algorithm animation system manipulates images with multiple views and provides a scripting facility. TANGO, on the other hand, has numerous descendent systems. XTANGO [Stasko 1992] is the direct descendent of the TANGO system. It is an X window version of TANGO and utilizes a path-transition paradigm to achieve smooth animation. XTANGO has another descendent system, POLKA and its front-end, Samba (information about POLKA and Samba can be found at the Web site http://www.cc.gatech.edu/gvu/softviz/parviz/polka.html). POLKA is designed to build concurrent animation for parallel programs. It is an object-oriented 2-D algorithm animation system and has extended to a 3-D system, POLKA 3-D. POLKA 3-D provides 3-D views and 3-D primitives such as cones, spheres, cubes and more. Users are not required to have prior knowledge of 3-D computer graphics to use POLKA 3-D. Samba is an interactive animation interpreter that reads ASCII commands and performs the corresponding animation actions. There is also a Java version of Samba called JSamba (see http://www.cc.gatech.due/gvu/softviz/parviz/samba.html).
Other popular algorithm animation systems include Zeus, Leonardo, CATAI, Mocha. Zeus [Brown 1991] was developed at Brown University and along with BALSA and BALSA-II, it was considered as one of the first major interactive software visualization systems. It supports multiple synchronized views and allows users to edit those views and change a data item's representation. Zeus is implemented in a multi-threaded and multi-processor environment, so it can animate parallel programs. Leonardo (see http://www.dis.uniromal.it/~demetres/Leonoardo/Overview/Overview.html) is an integrated environment for developing and animating C programs. It integrates the development and animation of C programs into the same environment together with extensive user control over the animation. CATAI (see http://wonderland.dia.unisa.it/catai/) is an animations system that animates C++ programs. It relies on distributed object technologies and allows several users share the same animation through a virtual classroom abstraction. CATAI animations are shown by smart Java clients. Communications and synchronization between the animation clients and the animated algorithm are ensured by a Java animation server that uses the CORBA technology. Mocha (see http://www.cs.brown.edu/people/jib/Mocha.html) is a distributed model with a client-server architecture that optimally partitions the software components of a typical algorithm animation system. It overcomes the problems inherent in the X window and the Java model. In the Mocha model, only the interface code is exported to the user machine, while the algorithm is executed on a server that runs on the provider's machine.
Earlier algorithm animation systems were platform-dependent. With the advent of new technology, popularity of the World Wide Web and evolution of the Java programming language, developers have shifted to build on-line algorithm animation systems, which have the advantage of platform-independence and open accessibility over earlier systems. Some developers also incorporated the use of multimedia in their systems. The use of algorithm animation systems was no longer confined to traditional classrooms or laboratory teaching but has now extended to distance education.
At present, very large number of algorithm animation systems have been developed in the last two decades. Most of the algorithm animation systems mentioned in this section are among the more popular and sophisticated systems currently used. They have been developed and used by their respective developers for educational purpose or empirical research. Some of these systems have a complex architecture and require specific supporting technology to run. We did not utilitise any of these systems to build our interactive parsing animation system; instead, we have evaluated other existing general purpose algorithm animation systems which were smaller in size and had simpler architectures. In the next section, we investigate the use of algorithm animation in education and analyze its effectiveness.