From the Abstract to the Concrete - Teaching Algorithms and Concepts with SVG Interactive Tools

Catherine R. Emond, Ulrike Stege, and Eric Manning
Department of Computer Science
University of Victoria
cemond@cs.uvic.ca, stege@cs.uvic.ca, and Eric.Manning@engr.uvic.ca

Extended Abstract

The understanding of algorithms is a crucial aspect of most computer science courses and also of interdisciplinary research between computer scientists and researchers in other areas (such as biology, geography, and economy). Understanding the design and analysis of algorithms and data structures also involves the ability to analyze algorithms, and to understand their underlying concepts. One aid to support the teaching of algorithms is their animation and visualization [1,2,4,8]. As an example for the visualization of general abstract concepts see the Plumb Design Interactive Thesaurus [9]. In this extended abstract we describe visualization tools that we developed as teaching aids for two different computer-science courses at the University of Victoria: a third-year course in Computer Architecture, CSc 350, and a second year course in Algorithms and Data Structures, CSc 225. Approaches to setting up the animation sequences are discussed, including usability issues. Examples of our animations are presented and methods of construction are discussed. The animation and visualisation tools we created support not only properties like web-accessibility and interactivity, but also allow the students to make predictions (e.g., during the process of an algorithm) and receive feedback. We begin with a brief history of algorithm and concept visualization, and illustrate why SVG is appropriate for this purpose.

Algorithm visualization (AV) technology can graphically illustrate how algorithms work [4]. AV can be used to help create a concrete visual manifestation of these algorithms and their underlying concepts, and accommodate the different learning styles that are encountered in classroom and research [10]. Research has shown that AV can assist the student in understanding algorithms [3]. It is most effective when it encourages students to engage actively in their own learning, especially through what-if analysis, predictive exercises, and programming exercises [4, 6].
In particular, "the presence of algorithm animations seems to make a challenging algorithm more accessible and less intimidating, thus leading to enhanced student interaction with the materials and facilitating learning." [5]. Current web-accessible AV technologies are usually JAVA based, and are often based on a client-server model (e.g., HalVis [3], JHAVÉ [6], and JSamba [11]). We decided not to use JAVA because we wanted visualizations that were easily embedded in both online web quizzes and/or Microsoft applications. We also required them to have: client-side scripting, quick download time, high quality graphics, user interaction, and open source standardised programming. We decided to create the visualizations with a combination of SVG, JavaScript, and HTML since this satisfied our requirements. Examples using SVG that come closest to algorithm interactive animations are the interactive cartography websites [7].

We created interactive animated algorithm and concept visualizations that encourage student participation for the following two courses, each of which has different requirements for their visualizations.

CSc 350 - Computer Architecture
Animations based on course text book illustrations. The professor can control the animation sequence during a class demonstration, and have the students make predictions about the next step to facilitate learning of the algorithm. The animation can be mounted on the web for student review. Example tools are
o Direct Mapped Cache [ex 1]
o Page Replacement Algorithm [ex 2]

CSc 225 - Algorithm and Data Structures
Animations accessed on line to help students prepare for, and complement the course's online quizzes. Combining the visualization with an HTML form input creates a predictive exercise - since the controls to animate the algorithm are only made available when the student successfully fills out the form. These animations are being embedded in the online quizzes, so that the student can work with the animations to answer questions. Example tools are
o Algorithm growth rate. [ex 3]
o Heap Data Structure [ex 4]

The graphics for the tools were first created in Adobe Illustrator 10 and saved as SVG. JavaScript was used for animation and interaction between the SVG and HTML form. (SMIL was not used for animation because the algorithm animations used multiple variables and interacted with HTML forms.) They are animations with hard coded parameters, but SVG combined with HTML form interaction encourages interactive prediction. The animation sequence can be controlled by the users and can be accessed at school or at home.

We plan to extend the SVG animated visualizations to general tools that allow to be used in any course that can have its concepts explained using graphs, flowcharts and visual mappings. We also plan to further develop these interactive graphics so that they allow the graphic content to be more accessible to visually impaired students by adding sound and voice to the animations. The interactive algorithms that we developed can be modified to also include audio interaction. This would allow the text user to interact with the graphics at a level their disability allows through visual cues, visual animation, zooming in, audio cues and audio description.

References

[1] Byrne, Michael D, Catrambone, Richard and Stasko, John T., " Do Algorithm Animations Aid Learning?", Graphics, Visualization, and Usability Center, Georgia Institute of Technology, Atlanta, GA, Technical Report GIT-GVU-96-18, August 1996.

[2] Georgia Institute of Technology, web page on algorithm animation (http://www.cc.gatech.edu/gvu/softviz/algoanim/algoanim.html).

[3] S. Hansen, D. Schrimpsher, and N. H. Narayanan "From algorithm animations to animation-embedded hypermedia visualizations", Proceedings of the World Conference on Educational Multimedia, Hypermedia & Telecommunications (ED-MEDIA'99), Association for the Advancement of Computing in Education, 1999.

[4] C. Hundhausen, S. Douglas, and J. Stasko, "A Meta-Study of Algorithm Visualization Effectiveness", Journal of Visual Languages and Computing, Vol. 13, No. 3, June 2002, pp. 259-290.

[5] C. Kehoe, J. Stasko, and A. Taylor, " Rethinking the Evaluation of Algorithm Animations as Learning Aids: An Observational Study", Graphics, Visualization, and Usability Center, Georgia Institute of Technology, Atlanta, GA, Technical Report GIT-GVU-99-10, March 1999.

[6] T. L. Naps, L. L. Norton, and J. R. Eagan, "JHAVÉ -- An Environment to Actively Engage Students in Web-based Algorithm Visualizations," in Proceedings of the SIGCSE Session, ACM Meetings (Austin, Texas, March 2000).

[7] A. Neumann and A. Winter, Vector-based Web Cartography: Enabler SVG http://www.carto.net/papers/svg/index_e.html

[8] Stasko, John T., " Using Student-Built Algorithm Animations as Learning Aids", Graphics, Visualization, and Usability Center, Georgia Institute of Technology, Atlanta, GA, Technical Report GIT-GVU-96-19, August 1996.

[9] Plumb Design, Visual Thesaurus, http://www.visualthesaurus.com/index.jsp.

[10] F. M. Williams (2002, July). "Diversity, Thinking Styles, and Infographics" Paper presented at the ICWES12 Conference, Ottawa, Canada.

[11] JSAMBA, algorithm animation system, Georgia Institute of Technology, http://www.cc.gatech.edu/gvu/softviz/algoanim/samba.html

Appendix

List of Examples/Tools
[ex 1] http://www.cs.uvic.ca/~cemond/AlgorithmAnimation/growthrate/graphform021303_1.htm
[ex 2] http://www.cs.uvic.ca/~cemond/AlgorithmAnimation/cache.html
[ex 3] http://www.cs.uvic.ca/~cemond/AlgorithmAnimation/PageReplacementAlgorithms.html
[ex 4] http://www.cs.uvic.ca/~cemond/AlgorithmAnimation/testForm010803a.htm