Algorithm Animation
Welcome to my website on Algorithm Animations (Sorting
Algorithms). I am currently a 3rd year student who is studying in
the Department of Computer Science in the University of Manchester. This site
is created for my final year project, Algorithm Animation.
Introduction
An algorithm
is a clearly specified set of instructions the computer will follow to solve a
problem. After a lecture on a course about algorithms, a student will normally
have a set of lecture notes containing pseudo-code and paragraphs of words
explaining the details of the workings of an algorithm. However, just by
reading these, a student might not be able to gain a good understanding of the
algorithm. Algorithm animation is therefore used as a teaching tool to solve
this problem. An algorithm animation allows us to visualise the behaviour of an
algorithm.
Aim of the Project
The aim of
this project is to develop a framework, using Java, to support the animation of
sorting algorithms. The reason as to why the scope of this project is limited
only to a particular type of algorithm, that is, sorting algorithms, and not
handle all the different types of algorithm animations is because of the time
constraint of this third year project. The system developed will have a generic
capability of implementing any form of sorting algorithm animations.
There are
two different kinds of users associated with this system, the viewer of the
animation, and the programmer who wants to use this framework to animate an
algorithm. The viewer is someone who wants to improve his understanding of the
algorithm. Viewers will be able to interact with the animation, via the
system’s graphical user interface, choosing either to watch the animation
running continuously or step by step. Steps of the algorithm will be explained
as the animation takes place. Viewers will not be required to have any
knowledge about the implementation of the system. On the other hand, the
programmer will be required to look into and understand the implementation of
the system. The system will provide a set of different representations of
algorithm features that programmers can choose from to animate their algorithms
more conveniently. The programmer will use or extend these components provided
by the system to create new animations of his algorithms.
Architecture of the System
The
architecture of this algorithm animation framework is divided into two
completely independent systems, namely, the Algorithm system and the Algorithm
Animation system. The algorithm execution will be handled by the algorithm
system while its animation will be handled by the animation system. The
approach taken to implement this framework is to allow the algorithm to execute
independently to completion in the algorithm system. While it is executing, the
algorithm will generate information that will be passed on to the animation
system. In turn, the animation system will use the information passed to it to
animate the algorithm. In order for this software to handle two independently
executing systems together, threads will be used. Therefore, the software will
have to manage two independently executing threads and pass information from
one thread to the other.
The
architecture of this system will follow an event driven approach. The
programmer will specify some ‘interesting events’. These events are the trigger
points in the code that will require animating. Examples of such events in a
sorting algorithm will be the comparison of the values of two elements to be
sorted, the swapping of their positions, and also the display of text to the
viewer explaining the step of the algorithm that just took place. The
programmer will add these animation events at appropriate places in the code of
the algorithm that requires animation. In order for algorithm animation to take
place, the algorithm executing in the algorithm system will generate these
events and store them in a queue. Following that, the animation system will
retrieve these events from the queue and use the information provided in the
events to animate the algorithm. The resulting animation will be displayed to
the viewer in the graphical user interface of the system. The figure above
describes this process. As there will be two separate threads accessing the
same queue, concurrency control for the queue is very important. The add
and remove method of the queue will need to be properly synchronised to ensure correct
operation of the queue.
Links: