|
|
© 1997 Copyright on this material is held by the authors.
A number of schools use algorithm animations in the curriculum. One way is to show prepared algorithm animations as a video supplement to a classroom lecture [2]. Another method is to have a prepared algorithm animation library for laboratory or off-time study [4]. Although these uses garner enthusiasm from instructors and students, empirical studies examining their pedagogical contribution have found mixed results [3].
This demonstration introduces an alternative application of algorithm animation technology--one in which students construct their own animations in order to better understand algorithms. In such an approach, it is critical that the algorithm animation construction system be very easy to learn and use. A complex, involved system may force students to expend the majority of their time and energy on the mechanics of building animations. Rather, the students should focus almost all of their effort on the design and expressive aspects of animation construction. An ideal algorithm animation system here would be one that is easy to use, not dependent on a particular programming language, but that still has a rich set of graphical primitives for students to build innovative, informative animations.
We have built such a system and it is called Samba. Samba is simply a front-end application program for the Polka software visualization environment [6]. Samba follows the approach of the ANIM system [1] in using a simple animation scripting language. Samba provides a much richer graphics environment, however. Commands exist to create and modify 2-D, color, objects in multiple animation windows. Below are a few example commands in the Samba scripting language:
line l2 0.1 0.1 0.2 0.2 green thin
rectangle r3 0.1 0.9 0.1 0.1 blue solid
text title 0.0 0.0 0 black Hello
moveto l2 r3
bg pink
jumprelative title 0.4 0.4
circle 17 0.8 0.8 0.1 red half
delete r3
{
color l2 red
color 17 purple
}
exchangepos title l2
set all3 l2 title 17
Each line defines a new command. The first field specifies the command type. On an object creation command (line, circle, text, etc.) the second field specifies an ID that can be used in subsequent modifier commands. Trailing fields specify parameters to the commands. The bracket notation, "{" and "}", specifies a concurrent block of commands.
Samba simply reads a series of these types of commands and displays the corresponding animation. To generate animations, students intersperse print (output) statements in their programs at key points, thus producing a meaningful script or trace.
The primary focus of this demonstration is to describe how Samba has been used as an instructional tool in classes. We have used the system three times in the undergraduate Design and Analysis of Algorithms course at Georgia Tech. Assignments were given in which students both implemented an algorithm and built an animation of it. Each animation assignment was weighted about twice that of a weekly written homework problem set.
Our experiences with these assignments has been very positive. The animations bring a new aspect to a very theoretical, conceptual class. Students enjoy building the animations and become competitive with each other, trying to outdo peers' animations. Simply put, the students appear to enjoy "seeing" the algorithms work. Surveys taken at course end indicate that the students felt the animations helped them understand the algorithms, that the animations were not difficult to build, and that the exercises were fun. When asked about the animation assignments, student replies included
"Not only did I have to know how to code it, I also had to think about how to relate it to another person--That made me really understand it in multiple dimensions."
"They provide an overall view of the algorithm that cannot be seen on a code level."
"It helped me to visualize what is going on. I lose track if I try to trace stuff in my mind. The animations kept me from losing track."
"The were challenging but yet doable. After completing them, it gave you a good sense of accomplishment."
"I wish more theory courses would use this approach."
Further, it appears that implementing and animating an algorithm brings a true understanding of it to the student. We believe this cognitive benefit can be attributed to a number of factors:
Figure 1 above shows a frame from an animation of quicksort built by a student in the Algorithms course. This demonstration showcases many such animations built by students in the course. It also conjectures why this construction process can be successful as a pedagogical aid.
For more details about Samba and its use, please see [5]. The system is available via the Web at http://www.cc.gatech.edu/gvu/softviz/algoanim/samba.html or via anonymous ftp at ftp.cc.gatech.edu included in with the Polka system, pub/people/stasko/polka.tar.Z.
[2] Brown, M.H. and Sedgewick, R. Techniques for algorithm animation. IEEE Software 2, 1 (Jan. 1985), 28-39.
[3] Byrne, M.D., Catrambone, R., and Stasko, J.T. Do algorithm animations aid learning? Technical Report GIT-GVU-96-18 , GVU Center, Georgia Institute of Technology, Atlanta, GA, Aug. 1996.
[4] Gloor, P.A. AACE - algorithm animation for computer science education. In Proceedings of the 1992 IEEE Workshop on Visual Languages (Seattle, WA, Sept. 1992), pp. 25-31.
[5] Stasko, J.T. Using student-built algorithm animations as learning aids. In Proceedings of the 1997 ACM SIGCSE Conference (San Jose, CA, Feb. 1997). An extended version is available as Technical Report GIT-GVU-96-19, GVU Center, Georgia Tech, August 1996.
[6] Stasko, J.T. and Kraemer, E. A methodology for building application-specific visualizations of parallel programs. Journal of Parallel and Distributed Computing 18, 2 (June 1993), 258--264.
|
|