1. Introduction/Thesis
Computer students introduced to tree algorithms via
animation programs requiring students to predict algorithm steps can outperform
control groups on tests measuring comprehension of the algorithms.
2. Theoretical Background
Algorithm animation is the use of graphics to dynamically illustrate details of a procedure. Algorithm animation is an area of research in the field of software visualization. Software visualization has been defined as “the use of the crafts of typography, graphic design, animation, and cinematography with modern human-computer interaction and computer graphics technology to facilitate both the human understanding and effective use of computer software” [Price 98].
For two decades, algorithms have been animated in the hopes that these visualizations would help learners understand algorithms. Baecker [Baecker 81] developed an influential film Sorting Out Sorting that animated algorithms used in several common sorts. Important software visualization systems in the history of algorithm animation include a system to debug Lisp by Lieberman [Lieberman 84a], BALSA by Marc Brown [Brown 84b], and TANGO by John Stasko [Stasko 90]. BALSA was a tool used by students at Brown University that allowed interaction with visualizations of their Pascal programs. TANGO was a conceptual framework and implementation of an animation system to animate C programs. TANGO research was performed at Brown University and Georgia Tech.
3. Previous Research in Algorithm Animation
Multiple surveys at Brown and Georgia Tech have shown enthusiastic student interest in algorithm animation. Bazik [Bazik 98] states, “Year after year students report … that visualization tools help them understand the concepts they are learning.” Badre [Badre 91] notes “Comments indicated a high perceived value for the [animation] system, with most students favoring its use as a teaching tool." In another study [Badre 92] the authors report that students were receptive and enthusiastic to animation use. In [Stasko 96], after student had built their own animations they reported that the animations were useful and helped them to understand the algorithms.
Do such visualizations help students learn? Only a few empirical studies have been performed. The results have been mixed. Lawrence [Lawrence 94] stated “Students who received the [animation] laboratory session … performed better … but not at significant levels.” Byrne [Byrne 96] stated, “The results from two experiments suggest that the benefits of animations are not obvious”. He also concluded “… the data from this study coupled with that of other prior formal empirical studies does show small, unreliable benefits for the animation.” No study has yet observed significant gains in test scores as a result of exposure to or the use of algorithm animations.
4. Goals of
the Research
If students are encouraged to interact with an animation by predicting the behavior of an algorithm being animated, will their involvement enhance their learning? This question will be investigated through two experiments that teach computer science students simple tree algorithms. The experiments will use heap sort and binary search tree algorithms.
Tom Naps’ JHAVČ visualization system (Java-hosted Algorithm Visualization Environment) is a client-server system that delivers algorithm visualizations over the Web. JHAVČ includes a heap sort visualization that will be used in one experiment. JHAVČ includes a quiz mode option. This option causes a window to appear, requesting the student to predict the action of the algorithm.
BST (Figure 2) is a java toolkit for animating tree algorithms [Ierardi 96]. This toolkit will be used for the second experiment. The BST applet will be enhanced with an intelligent tutor. The tutor will be used to train students in binary search tree terms, and in performing searches, deletions, and insertions on binary search trees. The tutor will require students to predict the performance of binary search algorithms. One treatment group in the binary search tree experiment will have access to the animation and the tutor. The other treatment group will interact with the animation, but not the tutor. The tutor will include a student model. The model will record student responses, and ask questions according to previous responses.
A pre-test will be administered to all groups to help establish that one group’s knowledge of the algorithm is relatively equivalent to the other groups. Control groups will be given access to static web pages instructing an algorithm, and then will be tested. Treatment groups will view the web pages, and then interact with animations. Treatment Groups A will not be asked to make predictions about algorithm steps. B Treatment Groups will be required to predict algorithm actions. Statistical comparisons will be performed between the results of the groups.
|
|
No Animation |
Animation w/o Prediction |
Animation with Prediction |
Heap Sort |
Control Group Static Web pages |
Treatment Group A JHAVČ |
Treatment Group B JHAVČ w/ Quiz Mode |
Binary Search Tree
|
Control Group Static Web pages |
Treatment Group A BST Toolkit |
Treatment Group B BST Toolkit |
5. Current
Status
During the summer of 2000, web pages were developed to teach the heap sort and to test students’ knowledge of the heap sort. Perl scripts were written to randomly assign students to groups and to record responses. The heap sort experiment is currently being conducted and should be completed by December 2000.
Java code to enhance BST with a tutor is currently under development and should be completed in early Spring 2001. The binary search tree experiment should occur during middle-late Spring 2001. Statistical analysis will be performed after the completion of the experiments.
6. Doctorial
Consortium Goals
5.
Bibliography
[Badre 92] Badre A., Beranek M., Morris J. and Stasko J., "Assessing program visualization systems as instructional aids," Tomek I., editor, Computer Assisted Learning, ICCAL '92, Volume 602 of Lecture Notes in Computer Science, SpringerVerlag, Wolfville, Nova Scotia, Canada, June 1992, pp. 87-99.
[Baecker 81] Baecker R., With the assistance of Dave Sherman, Sorting out Sorting, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. (Excerpted and "reprinted" in SIGGRAPH Video Review 7, 1983.) (Distributed by Morgan Kaufmann, Publishers.)
[Bazik 98] John Bazik, Roberto Tamassia, Steven P. Reiss, and Andries van Dam. “Software Visualization in Teaching at Brown University”. In Software Visualization: Programming as a Multimedia Experience, edited by John T. Stasko. Cambridge, Mass., MIT Press, 1998.
[Brown 84b] Brown M. and Sedgewick R., "A System for Algorithm Animation," Proceedings of ACM SIGGRAPH '84, Minneapolis, MN, July 1984, pp. 177-186.
[Byrne 96] Byrne M., Catrambone R. and Stasko J., "Do Algorithm Animations Aid Learning?", Technical Report GIT-GVU-96-18, GVU Center, Georgia Institute of Technology, Atlanta, GA, August 1996.
[Ierardi 96] Animation of algorithms. Interactive graphics for electronic textbooks and for teaching basic computer science. Includes the development of BST, a Java toolkit for the teaching of tree-based algorithms, and more recent work on interactive "textbooks". Internet WWW page, at URL <http://adsl-216-101-212-148.dsl.lsan03.pacbell.net/BST/index.html> (version current at 13-Apr-1996).
[Lawrence 94] Lawrence A., Badre A. and Stasko J., "Empirically evaluating the use of animations to teach algorithms," Proceedings of the 1994 IEEE Symposium on Visual Languages, St. Louis, MO, October 1994, pp. 48-54.
[Lieberman 84b] Lieberman H., "Seeing What Your Programs Are Doing," International Journal of Man-Machine Studies, Vol. 21, No. 4, October 1984, pp. 311-331.
[Naps 00] Naps, Thomas L., "JHAVČ—An Environment to Actively Engage Students in Web-based Algorithm Visualizations," in Conference Proceedings of the Thirty-first SIGCSE Technical Symposium on Computer Science Education, Austin, Texas, March 2000.
[Stasko 90] Stasko J., "TANGO: A Framework and System for Algorithm Animation," Computer, Vol. 23, No. 9, September 1990, pp. 27-39.
[Stasko 96] Stasko J., "Using Student-Built Algorithm Animations as Learning Aids," Technical Report GIT-GVU-96-19, GVU Center, Georgia Institute of Technology, Atlanta, GA, August 1996.
[Trochim 98] Trochim, William. The Research Methods Knowledge Base. Internet WWW page, at URL <http://trochim.human.cornell.edu/kb/index.htm> (version current at December 16, 1998).