Helping Learners Visualize and Comprehend Algorithms*
Steven R. Hansen, Air Command and Staff College
N. Hari Narayanan, Auburn University
Dan Schrimpsher, Teledyne Brown Engineering
The idea of using animations to illustrate dynamic behaviors of computer algorithms is over fifteen years old. Over a hundred algorithm animation systems have been built since then, with most developed in the belief that the animations would serve as effective learning aids for students. However, only recently have researchers started asking the question do algorithm animations really help? Unfortunately, results of experiments driven by this question have been disappointing. We believe that previous attempts at using animation to teach algorithm behavior were unsatisfactory not because of a flaw with animation as a technique, but because of the approach used to convey the animations. This paper provides an overview of our algorithm visualization research, based on the premise that a rethinking of algorithm animation design is required in order to harness its power to enhance learning. A novel theoretical framework for the design of effective algorithm visualizations, one which espouses embedding interactive analogies and animations in hypermedia to enhance contextual learning, is presented first. We then describe the architecture of HalVis, an implemented system based on this framework, and illustrate the various learning components of this architecture through an annotated slideshow of a visualization of the SelectionSort algorithm. Finally, a summary of results from eight empirical studies conducted over three years, involving more than 230 undergraduate students, is provided. These experiments demonstrated a statistically significant advantage of our framework over both traditional means of instruction and algorithm animations representative of extant research on this topic. They also led to a surprising discovery of the important role of interactive and animated analogies in priming learning about algorithms from subsequent visualizations.
Over nineteen years ago, with the unveiling of the movie Sorting Out Sorting at a Computer Graphics Conference (ACM SIGGRAPH-81), the idea of using graphics and animation to illustrate the dynamic behavior and functionality of computer algorithms was born. Algorithm animations appeared to hold great promise as instructional aids, with many dozens having been built since then, such as Balsa (Brown, 1988) and Tango (Stasko, 1990). Most were developed in the belief that algorithm animations would serve as effective supplements to lectures for students to learn about algorithms. This belief has a strong intuitive basis. Students have always had a relatively difficult time understanding abstract mathematical notions, especially when these included dynamics of how algorithms manipulate data, so concretizing these notions graphically and animating them to illustrate the dynamics ought to improve learning.
Although research on designing and deploying algorithm animations spans almost two decades, only recently have researchers started asking the question do algorithm animations really help? Dozens of experiments have been conducted to test whether algorithm animations lead to improved understanding of algorithms. Hundhausen (1997) presents an excellent summary of the results of 29 empirical studies pertaining to the comprehension efficacy of algorithm animations and, more generally, software visualizations. Unfortunately, all one can say about this accumulated evidence is that the results, at best, are mixed. While animations are enthusiastically received by the students, none of the studies has proven conclusively that these visual presentations actually improve learning (Badre et al., 1991; Byrne, Catrambone & Stasko, 1996). The following quotation succinctly expresses the frustration felt by researchers working in this area: "Unfortunately, the viability of algorithm animations as instructional aids remains rooted in intuition. No substantive empirical evidence has ever been presented to support these claims" (Stasko, Badre & Lewis, 1993). Is this because animation is an ineffective teaching tool? Intuition tells us that this is not likely.
2. Rethinking Algorithm Animations - From Animations to Visualizations
Research presented here is based on the premise that animations are indeed useful. We believe that previous attempts at using animation to teach algorithm behavior were unsatisfactory not because of a flaw with animation as a technique, but because of the approach used to convey the animations. Hence, a rethinking of algorithm animation design is required in order to harness its power to enhance learning. Theoretical foundations of the resulting novel approach to algorithm visualization are based on research in several areas:
Drawing from these sources, we have developed a framework for the design of algorithm visualizations and a corresponding software system. The key idea is to embed algorithm animations at various levels of abstraction inside a hypermedia environment. Distinctive features of our design framework and their rationale are described below.
3. System Architecture
We built a system, called HalVis (Hypermedia Algorithm Visualizations), as a proof-of-concept and a prototype for the empirical evaluation of the framework presented in the previous section. It is implemented using Asymmetrix ToolbookTM and employs all the features described previously. Visualizations of four popular sorting algorithms (BubbleSort, SelectionSort, MergeSort and QuickSort) and one common graph algorithm (Dijkstra's Shortest Path algorithm) were created for experimental purposes. Each visualization consists of the five modules (see Figure 1) described below.
HAlVis Selection Sort Example available for download:
Powerpoint file (4.8 MB)
For Windows: Zip file (2.9 MB) of the Powerpoint file.
For Mac: HQX (2.9 MB)
Or, view as web pages (image quality is lower than the downloadable files).
Figure 1. HalVis Architecture.
4. Experiments with Hypermedia Algorithm Visualization
We conducted a series of eight experiments over three years, involving 232 computer science undergraduate students as subjects. These experiments had two primary goals. The first was to evaluate the effectiveness of hypermedia visualizations of algorithms, specifically to validate our hypothesis that visualizations designed according to our framework are more effective than traditional means by which students learn about algorithms. The second was to determine the differential contributions of various features of HalVis to learning effectiveness. In each of the experiments, subjects were randomly divided into two (or four) matched groups. All groups took a pretest that measured their prior knowledge, learned one or more algorithms under different experimental conditions (using full or partial versions of HalVis or by a traditional method), and then took a posttest that measured their knowledge improvement. Students were tested on their ability to recognize and reorder pseudocode descriptions of algorithms, mentally simulate algorithmic operations, and predict resulting data structure changes. In these studies, we did not differentiate between visual and verbal learners since HalVis contains rich textual and visual presentations to support both kinds of learner dispositions. What follows is a summary of findings from these experiments. Other publications (Hansen, 1999; Hansen, Schrimpsher & Narayanan, 1998; Hansen, Schrimpsher, Narayanan & Hegarty, 1998; Hansen & Narayanan, 2000) contain additional experimental details.
Table 1 lists information about these experiments, showing the level and number of students involved in each, learning method used by the experimental groups and the extent of their learning, the algorithm(s) studied, and the statistical significance of results. For the first five experiments, group learning is indicated in parentheses by the mean percentage posttest score. For the next three experiments comparing different versions of HalVis, group learning is indicated by the mean percentage of pretest to posttest score improvement.
Experiment I showed that hypermedia visualization is more effective than a textbook for learning an algorithm. This result was successfully replicated in Experiment II using more advanced students. Experiment III compared learning from HalVis to learning from a compilation of the best algorithm descriptions (extracted from 19 textbooks published between 1974 and 1997) followed by problem solving activities. While the posttest averages favored the HalVis group, the difference between the two groups is not statistically significant in this case. This experiment indicated that interactive visualization could be as effective as learning from carefully crafted text, when problem solving followed that textual learning.
Experiment IV was designed to compare and evaluate how algorithm visualization (AV) and conventional classroom lectures interact and contribute to student learning. Our hypothesis was that AV alone would assist learning more than a lecture. If so, it follows that AV used in conjunction with lecture should assist learning even more. We used a 100-minute live classroom lecture, by a computer science faculty known for his teaching ability, delivered in two consecutive class sessions. Participants were second year computer science students at Auburn University, divided into two matching groups. One group used HalVis before attending the lecture (called the visualization-lecture VL group) and the other group used HalVis after the lecture (called the lecture-visualization LV group). Having both groups attend the same lecture eliminated variations that can occur in different lecture sessions, while allowing common interactions with the teacher. A first posttest was given between the two phases, and a second posttest was given after both phases. The first posttest results (shown in the table) indicated that the VL group learned significantly more from HalVis than the LV group from the lecture. Following a session with HalVis, the VL group's average posttest score was 70% compared to 44% for the LV group. The second posttest results showed that after receiving both the lecture and the visualization, both groups performed at the same level (72%). These results suggest that interactive visualizations can have a significantly higher learning impact than a lecture, and that a combination of both is even better.
Experiment V compared the effectiveness of learning from HalVis to learning from an algorithm animation typical of extant research on this topic. One of the most mature, widely reported, and publicly available algorithm animation platforms is the Tango software suite developed by Stasko (1997). The Tango software distribution contains a library of animated algorithms, including eight animations of the Shortest Path algorithm. Of these eight, we selected one that appeared to be the most complete, easiest to understand, and which most closely matched the features of the HalVis system, as a representative animation. One group of students interacted with HalVis and the other group interacted with the Tango animation. The second group was also provided with a textual description of the algorithm, to which the HalVis group did not have access. On the posttest, the HalVis group averaged 89% while the Tango group averaged 71%, indicating that a hypermedia algorithm visualization is more effective than a mere algorithm animation.
With five studies demonstrating the learning benefits of HalVis, we next asked the question: which features or modules of HalVis are producing the observed learning benefits? One approach to answering this is to build different versions of HalVis by selectively eliding specific features or modules, and then to experimentally compare these versions against the original. We designed and carried out three such studies. In Experiment VI we identified three features as most likely to have an impact on learning animation chunking, highlighting steps of the pseudocode, and questions (both ticklers and articulation points). We built three versions of the QuickSort algorithm visualization in HalVis, with each of these features removed. Four groups of students worked with the full and three elided versions. They were tested for their knowledge of the algorithm before and afterwards. As seen in the table, the HalVis group learned the most, followed by the group that did not get highlighted steps of the pseudocode, the group that did not get the questions, and the group that saw one-shot animations with no chunking. While these results did not attain statistical significance, the trend indicates that animation chunking may be the most important feature, followed by questions and highlighting steps of the algorithm in tandem with the animations.
Experiments VII and VIII were designed to reveal learning contributions of the three modules of HalVis Conceptual View, Detailed View and Populated View. In Experiment VII four matched groups of students interacted with one of four versions of HalVis illustrating the QuickSort algorithm a complete version (CDP version: all three views) and three elided versions (DP version: Conceptual View removed; CP version: Detailed View removed; and CD version: Populated View removed). Our hypothesis was that the most important view was the most information rich view the Detailed View. We also expected that the Populated View would follow in significance and that the contribution of the Conceptual View would be the least since it contained the least amount of algorithm-specific information. As expected, the group that received all three HalVis views performed the best. However, the groups that performed at the next level were not the ones exposed to the Detailed View but rather the groups that interacted with the Conceptual View. Perhaps the most noteworthy observation from this experiment is the effect of the Conceptual View in apparently priming the learning of information presented in subsequent views. The groups that interacted with the Conceptual View in any combination with other views performed more than twice as better as the group that lacked the Conceptual View.
Experiment VIII isolated and compared each of the three views. Its procedure was identical to that of Experiment VIII, with four matched groups of participants. The CDP group worked with a full version of HalVis illustrating Dijkstra's Shortest Path algorithm. The C group worked only with the Conceptual View of this algorithm. The D group worked only with the Detailed View of this algorithm. The P group worked only with the Populated View of this algorithm. Our hypothesis was that the Detailed View would prove to be the most valuable because of the amount of information it provided. We were uncertain as to how impacts of the other views would get ranked, since neither the Populated View nor the Conceptual View contained the volume or depth of information available in the Detailed View. As expected, the CDP group outperformed the others, followed closely by the D group. Interestingly, the C group outperformed the P group by 21%. It is illuminating to note how well the C group did with the limited amount of information (only the analogy) that they received. This reinforces the important role of interactive and animated analogies in learning about algorithms from visualizations.
This paper contains an overview of algorithm visualization research conducted at the Intelligent & Interactive Systems Laboratory at Auburn University over the last three years. This work was motivated by the present state of affairs in algorithm animation research. While the idea of using animations to illustrate the dynamic behaviors of computer algorithms is nearly two decades old, experiments intended to demonstrate the learning benefits of traditional algorithm animations have mostly produced disappointing results. We based our work on the premise that a rethinking of algorithm animation design is required in order to harness its power to enhance learning. The resulting theoretical framework for the design of effective algorithm visualizations, the architecture of HalVis an implemented system based on this framework, and a summary of eight empirical studies are presented. Collectively, these experiments provide statistical validity to the hypothesis that hypermedia algorithm visualizations can be significantly more effective than traditional teaching methods and algorithm animations, considered in isolation. They also led a surprising discovery of the important role of interactive and animated analogies in priming learning about algorithms from subsequent visualizations. More information on this research is available at our group's web site: http://www.eng.auburn.edu/csse/research/research_groups/vi3rg/vi3rg.html .
Badre, A., Beranek, M., Morris, J. M. & Stasko, J. T. (1991). Assessing program visualization systems as instructional aids. (Technical Report No. GIT-GVU-91-23). Atlanta, GA: College of Computing, Georgia Institute of Technology.
Brown, M. H. (1988). Exploring algorithms using Balsa-II. Computer, 21(5): 14-36.
Byrne, M., Catrambone, R., & Stasko, J. T. (1996). Do algorithm animations aid learning? (Technical Report No. GIT-GVU-96-18). Atlanta, GA: College of Computing, Georgia Institute of Technology.
Chi, M.T.H., Bassok, M., Lewis, M., Reimann, P., & Glaser, R. (1989). Self-explanations: how students study and use examples in learning to solve problems. Cognitive Science, 13: 145-182.
Crosby, M., & Stelovsky, J. (1995). From multimedia instruction to multimedia evaluation. Journal of Educational Multimedia and Hypermedia, 4(2/3): 147-162.
Daily, B. (1994). Multimedia and its impact on training engineers. International Journal of Human Computer Interaction, 6(2): 191-204.
Douglas, S. A., Hundhausen, C. D., & McKeown, D. (1995). Toward empirically-based software visualization languages. In Proceedings of the 1995 IEEE Symposium on Visual Languages (pp. 342-349). Los Alamitos, CA: IEEE CS Press.
Hansen, S. R. (1999). A framework for animation-embedded hypermedia visualization of algorithms. Unpublished Ph. D. Dissertation, Auburn, AL: Dept. of Computer Science & Software Engineering, Auburn University.
Hansen, S., & Narayanan, N. H. (2000). On the role of animated analogies in algorithm visualizations. In Proceedings of the International Conference of the Learning Sciences (to appear), Mahwah, NJ: Lawrence Erlbaum Associates.
Hansen, S., Schrimpsher, D., & Narayanan, N. H. (1998). Learning algorithms by visualization: A novel approach using animation-embedded hypermedia. In Proceedings of the International Conference of the Learning Sciences (pp. 125-130), Charlottesville, VA: Association for the Advancement of Computing in Education.
Hansen, S., Schrimpsher, D., & Narayanan, N. H. (1999). From algorithm animations to animation-embedded hypermedia visualizations. In Proceedings of the World Conference on Educational Multimedia, Hypermedia & Telecommunications (ED-MEDIA'99), Charlottesville, VA: Association for the Advancement of Computing in Education.
Hansen, S., Schrimpsher, D., Narayanan, N. H., & Hegarty, M. (1998). Empirical studies of animation-embedded hypermedia algorithm visualizations. (Technical Report No. CSE98-06). Auburn, AL: Dept. of Computer Science & Software Engineering, Auburn University.
Hmelo, C. E., & Guzdial, M. (1996). Of black and glass boxes: Scaffolding for learning and doing. In Proceedings of the International Conference of the Learning Sciences (pp. 128-134). Charlottesville, VA: Association for the Advancement of Computing in Education.
Hundhausen, C. D. (1997). A meta-study of software visualization effectiveness. Unpublished comprehensive examination paper. Eugene, OR: Dept. of Computer Science, University of Oregon. Available at http://www.lilt.ics.hawaii.edu/%7Ehundhaus/writings/MetaStudy.pdf.
Kehoe, C. M., & Stasko, J. T. (1996). Using animations to learn about algorithms: An ethnographic case study. (Technical Report No. GIT-GVU-96-20). Atlanta, GA: College of Computing, Georgia Institute of Technology.
Lawrence, A. W., Badre, A. N., & Stasko, J. T. (1994). Empirically evaluating the use of animations to teach algorithms. In Proceedings of the IEEE Symposium on Visual Languages (pp. 48-54). Los Alamitos, CA: IEEE CS Press.
Narayanan, N. H., & Hegarty, M. (1998). On designing comprehensible interactive hypermedia manuals. International Journal of Human-Computer Studies, 48: 267-301.
Rappin, N., Guzdial, M., Realff, M., & Ludovice, P. (1997). Balancing usability and learning in an interface. In Proceedings of the ACM Human Factors in Computing Systems Conference (CHI'97) (pp. 479-486). New York, NY: ACM Press.
Recker, M., Ram, A., Shikano, T., Li, G., & Stasko, J. T. (1995). Cognitive media types for multimedia information access. Journal of Educational Multimedia and Hypermedia, 4(2/3): 183-210.
Stasko, J. (1990). TANGO: A framework and system for algorithm animation. IEEE Computer, 23(9): 27-39.
Stasko, J. (1997). Using student-built algorithm animations as learning aids. In Proceedings of the SIGCSE Technical Symposium on Computer Science Education (pp. 25-29). New York, NY: ACM Press.
Stasko, J., Badre, A., & Lewis, C. (1993). Do algorithm animations assist learning? An empirical study and analysis. In Proceedings of the INTERCHI'93 Conference (pp. 61-66). New York, NY: ACM Press.
This research has been supported by the National Science Foundation under contracts CDA-9616513 and REC-9815016. We gratefully acknowledge the advice of Mary Hegarty, Department of Psychology, University of California at Santa Barbara, who serves as an expert consultant on experiment design and data analysis to this project. Finally, the experiments could not have been carried out without the voluntary participation of students from the following courses: Fundamentals of Computer Science II (CSE 220) and Fundamental Algorithm Design and Analysis (CSE 360).
* This is a revised and extended version of the paper "From algorithm animations to animation-embedded hypermedia visualizations" that appeared in the Proceedings of the World Conference on Educational Multimedia, Hypermedia & Telecommunications (ED-MEDIA'99), Association for the Advancement of Computing in Education (Hansen, Schrimpsher & Narayanan, 1999).
********** End of Document **********
|IMEJ multimedia team member assigned to this paper||Yue-Ling Wong|