Keywords: algorithm visualization, interactive graphics, web design
Catherine Emond has just completed her BSc in Computer Science at the University of Victoria. This has given her the skills needed to learn how to create the SVG interactive algorithm visualizations described in this paper. The motivation to animate these visualizations derives from her background in modern dance/choreography, automotive mechanics and industrial automation.
Ulrike Stege received her doctoral degree in Computer Science (2000) from ETH Zurich. She is now an Assistant Professor at the Department of Computer Science of the University of Victoria. Her current research interests include Computational Biology, Parameterized Complexity, the Design of Heuristics, Graph Theory, and Cognitive Psychology.
Eric Manning received a Ph.D in Electrical Engineering (1965) from the University of Illinois. He was then Assistant Professor and Ford Postdoctoral Fellow at the Massachusetts Institute of Technology, Cambridge, and a Member of Technical Staff at the Bell Telephone Laboratories, Inc. He then joined the University of Waterloo and then the University of Victoria where he was Dean of Engineering, and Professor of Electrical & Computer Engineering and Computer Science. Since 2001 he has been the Nortel Networks / New Media Innovation Centre Professor of Network Performance at the University of Victoria, and NewMIC (New Media Innovation Centre) Scientist in Network Performance. He has conducted research in the areas of fault diagnosis in digital systems, computer networks, distributed processing, distributed simulation, and multimedia Quality of Service, and has written over 100 articles on these topics. He is a Fellow of the IEEE (Institute of Electrical and Electronics Engineers) and is cited in Who's Who in America and in Who's Who in Canada. He is currently studying redesign of the Internet to carry multimedia.
The understanding of algorithms is a crucial aspect of most computer science courses. It is also a crucial aspect of interdisciplinary research involving computer science. Understanding the design and analysis of algorithms and data structures 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. In this paper we describe visualization tools that we developed as teaching aids for two different computer -science courses: a third-year course in Computer Architecture and a second year course in Algorithms and Data Structures. 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 visualization tools which we created support not only properties like web-accessibility and interactivity, but also allow the students to make predictions and receive feedback.
Usability Design Goals
CSc 350: Computer Architecture - Examples
MIPS Addressing Mode
State Machine versus Microsteps
Direct Mapped Cache
CSc 225: Algorithms and Data Structures - Examples
Heap Data Structure
Growth Rate Graphs
Binary Search Pseudocode
The understanding of algorithms is a crucial aspect of most computer science courses, as well as of interdisciplinary research involving computer scientists and researchers in areas as biology, geography, and economics. Crucial issues for understanding the design and analysis of algorithms are the ability to analyze algorithms, and to understand their underlying and data structures and concepts. In this article we present different SVG (Scalable Vector Graphics) tools that are designed to (1) aid the teaching of algorithms in course of a lecture and (2) support and motivate student learning in such a course in an interactive way.
AV (Algorithm visualization) , is a form of software visualization [Pri93] , and is concerned with illustrating computer algorithms in terms of their high-level operations, usually for the purpose of enhancing computer science students' understanding of the algorithms' procedural behaviour [Hun02] . It can help create a concrete visual image of an algorithm and of its underlying concepts, and it can accommodate different learning styles [Wil02] . AV is most effective when it encourages students to engage actively in their own learning, as in programming and homework exercises (see e.g., [Hun02] , [Nap00] ). 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." [Keh99] . Also, AV can have increased pedagogical value when it is used in coordination with other learning materials, or accompanies other material which explains how the animation simulates an algorithm's operations.
The movie Sorting Out Sorting by R.M. Baecker is the first major example of AV [Bae81] , [Bae98] . Examples for further algorithm animations are BALSA (Brown ALgorithm Simulator and Animator) [Bro84] , [Bro88] , TANGO (Transition-based Animation GeneratiOn) [Sta92] , XTANGO [Sta92] , POLKA [POLKA] , Samba [SAMBA] , JSamba [JSAMB] , Zeus [Bro91] , Leonardo [Cre97] , CATAI [CATAI] , and Mocha [Bak95] . With the usability of the World Wide Web, the use of algorithm animation systems is no longer confined to traditional classrooms or laboratory teaching, but can be easily extended to interactive use outside lab and class room as well as to distance education. Current web-accessible AV technologies are usually JAVA based, and are often based on a client-server model (e.g., HalVis [Han99] , JHAVE [Nap00] , and JSamba [JSAMB] ). In [You00] an overview of existing animation and visualization tools is given and the use of algorithm animation in education is investigated and its effectiveness is analyzed.
In this article 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 not only support 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.
The difficulty encountered by students trying to conceptually translate static textbook diagrams into the dynamic processes which the diagrams represented was the motivation for creating the visualization tools discussed in this paper. Our goal was to create AV’s that would supplement textbooks and class notes  . The visualizations were to be (1) embedded in or linked to Microsoft PowerPoint slides for class lectures, and (2) embedded in HTML pages for Web viewing.
The visualization tools discussed in this paper are created as animations that focus on specific micro-level algorithmic and conceptual operations. These operations are referenced in the course text and slides  and then supplemented and motivated by the AV's . The textbook and slides in conjunction with the visualizations effectively create a multimedia presentation of algorithms and concepts, which can always be available to the students via the textbook and the Web, and can be used for reading assignments and study aids.
Our design goal was to provide the student with the ability to view the visualization with at least one type of animation. Most of the AV's allow the sequencing of discrete snapshots of the algorithm or concept process, and a few also provide smoothly running animation. In the last three AV's created, Heap Data Structure , Growth Rate Graphs , and Binary Search Pseudocode , the students are first required to successfully answer a series of predictive questions or enter the data correctly before they are allowed to run the animation. This helps prevent the student from running the animation without understanding the algorithmic and conceptual operations presented in the animation.
In the design of the visualizations, three different types of design heuristics influenced us:
The heuristics from these categories most helpful to our AV design were feedback, error recognition, animation control, help documentation, and accessibility.
Feedback to the student of the AV's system status is very important since the students can not run the more advanced visualization animations before they have correctly input the data set or completed answering the predictive question set. Feedback and error recognition is provided through colour and text change, cursor style change, pop–up text and pop-up alert windows.
Various methods can be used to control the animations:
Although the AV's do not have a reverse control for the discrete animation sequences, the sequences are short enough that a student can quickly step through the discrete sequences a second time and stop at the desired frame  .
The first seven AV's were primarily designed for in-class presentation, so no help documentation was initially provided, since the instructor was taught to use the visualization. However, when the AV's were embedded in HTML pages for Web accessibility, written help documentation was either inserted in the HTML page, or a link to a separate help page was added. This allowed the students to use the visualizations without prior in-class instruciton.
The first seven visualizations CSc 350: Computer Architecture - Examples were created for the University of Victoria CSc 350 course Computer Architecture  . The AV's were primarily created for in-class PowerPoint presentations, and secondarily for website access. The SVG cleanly replicated diagrams of the course textbook or diagrams created by the course instructor. These seven AV's were created as sets of image layers  that were manipulated by the user to incrementally step through the images, which allowed one layer to be visible at a time. This was useful in class presentations where the professor could control the sequencing speed of the images according to class needs.
The last three AV visualizations were created for the University of Victoria CSc 225 course Algorithms and Data Structures  , and more closely follow the recommendations and insights of hypermedia/multimedia AV system research [Nap00] , [Han99/2] , which recommends encouraging both student interactivity and critical thinking through the use of predictive analysis. These last three AV 's, Heap Data Structure , Growth Rate Graphs and Binary Search Pseudocode , which have been primarily designed for web accessibility, require the students to input the data or to predict the order of the data sequence before they are allowed to run the animation. The animation of the algorithm is the reward for learning the specific operational details of the algorithm, with immediate feedback provided to the students as to whether their predictive answers were correct or not. In the last example, the students can view the correct answer after they have attempted to arrange the data into the correct sequence.
Unlike the first group of AV's that used hard coded data parameters that could not be modified by the student, the Heap Data Structure and Growth Rate Graphs visualizations do not rely on hard coded parameters but allow the student to input new data through HTML forms to modify the presentation. The Binary Search Pseudocode visualization uses hard coded data parameters but allows student mouse events to reposition SVG objects so that the student can rearrange the data into the correct order. These most recently developed AV's encourage more complex interactivity than the earlier AV through the addition of animation controls, data alteration, and predictive questions. The articulation milestones created by the predictive questions encourage critical thinking and active participation in the visualizations.
NOTE: Clicking on the link below each SVG figure will provide a full-screen, interactive version of the depicted image.
Note the hand cursor. These are created by wrapping the <g> grouping elements with link <a></a> elements so that the browser was "fooled" into believing these were links. Although the documentation at http://www.w3.org/TR/SVG/interact.html#CursorProperty indicates that the cursor property could be modified in SVG , I was not successful implementing this method.
In this graphic, all the layers are visible. When a text object is clicked, the mouse event changes the colour property of another object. The elements are grouped so that only the text is the link, not the box or circle surrounding the text. In Figure 2 below, click on the Microstep stepnames to highlight the corresponding Finite State Machine nodes, or click on the node text to highlight the corresponding Microstep.
Figure 2: Microsteps/Finite State Machine: A comparison of MIPS instruction classes 
The full interactive version is available here: StateMachine.html
This AV connects the two concepts of State Machine and Microsteps through comparison. These diagrams were adapted from the course textbook, which had the diagrams on separate pages. Comparing the two system diagrams was difficult yet important for understanding the course material. The diagrams are crowded when viewed on a computer monitor, but when supplemented with the textbook allows the student to quickly understand the connection between the two systems.
Figure 3: Network Pipelining
The full interactive version is available here: netwrkpipeline.html
The intricate layer management of this graphic show above in Figure 3 , is again controlled by mouse click events. Each colour change is created by object visibility property changes. Each object is a collection of xlink:hrefs attributes to predefined objects. This allows for the simultaneous animation of both network diagrams.
Figure 4 below is another example of layer management. On mouse click events the SVG object fill and stroke properties change. Since more than one microstep can share the same bus path, the code has to check whether other microsteps are active before changing bus path colours. A problem that arises from this type of image management is that the code becomes very customized and is not easily recycled.
Figure 4: Control in Action: Simple Machine 
The full interactive version is available here: SimpleMachine.html
Figure 5: Comparison of Page Replacement Algorithms 
The full interactive version is available here: Page.html
Figure 6 is an example of simple image management where mouse click events cause the SVG objects’ visibility properties to be modified. Again, the graphic was created for in-class demonstration, so the sequence of events is not controlled by the code but by a single knowledgeable user (the instructor). Therefore, the instructor must mediate the interaction of the class and the AV .
Figure 6: Data Dependencies in Program Execution Order 
The full interactive version is available here: datadep.html
The algorithm is sequenced in Figure 7 by creating a new text node and replacing the current text with new text. This is the first example which we created that utilized parameter input to create the next frame in the animation sequence. The parameters are hard coded, which does not allow for student modification of the data. Basic help documentation is provided for the student, which allows this AV to be used without instructor mediation.
Figure 7: Direct Mapped Cache
The full interactive version is available here: cache.html
The last three AV's have links to instruction help pages, allowing the student to work through the animation exercises without prior teacher explanation. The SVG are embedded in HTML files since data input is achieved with HTML forms. Because of this embedding in HTML , these visualizations can be viewed at the respective URL's (Uniform Resource Locator) provided. We recommend using Internet Explorer Version 6+ to view them.
This is the first AV that allows the student to input different data sets. The SVG diagram and an HTML form are placed in a HTML table. Data is entered in the form and the values used to create text nodes that replace the empty text nodes in the SVG diagram heap tree. The AV contains both SVG and HTML buttons  , with the HTML form button controlling student data input and help instruction access, and the SVG buttons controlling the heap data structure.
The graphic setup is similar to Heap Data Structure , but the student data input is restricted to drop-down menu choices to ensure data consistency for data checking. The colour and text change to inform the student of correct data predictions. When the growth rate function order has been correctly chosen, SVG buttons appear for both incremental stepping and smooth animation through the function sequence. Note: once one of the SVG buttons is chosen, the other button is rendered invisible to prevent mouse event conflicts.
The AV window is split into 3 HTML frames:
Calling objects and methods across frames requires "bubbling" up the objects and methods from the SVG document where they originate to the parent HTML document, and then to the frameset HTML document, where the other HTML frames can access them.
All buttons in this visualization are created in SVG , which means the colours of the buttons are not restricted to the default HTML form button colours, hence the lime green.
In this article we presented examples of visualization tools to support the teaching of algorithms that we can separate in two categories: In-class aids (MIPS addressing mode, State Machine versus Microsteps, Network Pipeline, Simple Machine, Page Algorithm, Data Dependencies, Direct Map Cache) that support the instructor and interactive student learning aids (Heap Data Structure, Growth Rate Graphs, Binary Search Pseudocode). Evaluation of the three latter tools is still in progress and will be conducted in the next Spring term (January-April 2004).
CSc 225: Algorithms and Data Structures
CSc 350: Computer Architecture
Applications used in AV development:
In the AV example descriptions the terms layer and frame are used interchangeably. Adobe illustrator drawings are composed of objects or groups of objects that are positioned on layers. When the drawings are saved as SVG files, each layer becomes an SVG object that can be used as an animation frame, by sequencing object property modifications.
These graphics that were used as basis for the SVG are © 1998 Morgan Kaufmann Publishers/Elsevier Science (USA). Reprinted with permission from Computer Organization and Design: The Hardware/Software Interface 2E.
Even though SVG does not have a designated button tag like HTML , we will refer to the SVG objects in the AV 's that look like buttons as "buttons".
XHTML rendition created by gcapaper Web Publisher v2.0, © 2001-3 Schema Software Inc.