Web Based Visualization

Introduction

This page contains links to information on algorithm visualization and animation on the Web. It grew out of a workshop held at Uppsala, Sweden in June, 1997: Integrating Technology into Computer Science Education, sponsored by SIGCSE and SIGCUE special interest groups of the Association for Computing Machinery. Participants were: Mail to the group
Jiménez-Peris, McNally, Proulx, Bergin, Patiño-Martínez, Naps, Tarhio
Under construction

1 Non-interactive visualizations hyperlinked into HTML documents

This technique essentially amounts to an on-line version of a traditional text book with the advantage of being able to incorporate hypertext links to other Web sites. Since it does not take advantage of the dynamic nature of algorithm visualization, it is no doubt the technique of least interest to us in our deliberations. Nonetheless, there are some excellent sources of material that can help students understand difficult concepts.

For example, Thomas Niemann of Santa Cruz, California has authored a very nice explanation of various sorting algorithms. This explanation includes very understandable discussions of the efficiencies of the algorithms and is accompanied by a large collection of detailed figures. Niemann's work can be found at http://www.geocities.com/SoHo/2167/book.html.

José C. Castillo, Mourad Fahim, and Lúcio C. Tinoco of Virginia Tech have created a presentation of operations on binary tree structures that includes a variety of static visualizations created by Macromedia Director 4.0. This presentation includes textual definitions of the operations, pseudo-code versions of key algorithms, and visualizations that are linked to relevant portions of the pseudo-code. Their work may be viewed at http://wasabi.cs.vt.edu/~josec/sciviz/index.html.

2 Interactive visualizations running on client-specific software

Harriet Fell, Viera Proulx, and Richard Rasala of Northeastern University have prepared a variety of Mac-specific visualizations for CS1 and algorithms and data structures courses. They may be downloaded from http://http://www.ccs.neu.edu/courses/cpp. Once downloaded, the visualizations are interactive but they require Macintosh-specific software to run.

Marta Patiño-Martínez and Ricardo Jiménez-Peris at Universidad Politécnica de Madrid have a set of visualizations on recursion and operations on linked lists created with Macromedia Authorware. They animate particular algorithms showing the source of different subprogram calls in different windows as well as a visualization of the state of dynamic memory. The visualizations provide a menu to select different data sets. A web page with this animations can be found at http://lml.ls.fi.upm.es/VisualGroup/Animations.html.

Another approach to the distribution of interactive, client-specific visualizations is taken at the site http://SunSITE.univie.ac.at/Spreadsite/. Available here are a variety of scientific animations that require Excel spreadsheet software. If the client has Excel, the client system's browser may be configured to immediately launch the Excel-based animation when the corresponding spreadsheet is downloaded.

3 Interactive visualizations using CGI scripts

In his Web page at http://www.cs.rpi.edu/projects/STL/htdocs/node50.html, Ken Zalewski illustrates several sorting algorithms by having the Web surfer fill out an HTML form to provide input to the sorting algorithm and then providing a visualization of the algorithm in a window opened on the client machine. Here, the interaction between the viewer is very limited because of the form-based input involved.

4 Interactive visualizations running Java applets

Glenn Rowe of University of Dundee provides a nice illustration of the quicksort algorithm accessed via http://orange.mcs.dundee.ac.uk:8080/CS202/tuts/mosaic/sorting/QuickDemo/QuickSortDemo.html. Viewers are allowed to enter a small set of data and then watch the algorithm in a continuous play or one-step-at-a-time mode.

Yin-so Chen of the University of Washington has developed Java-based illustrations of five classic sorting algorithms. Although Chen's illustrations only run for small sets of data, his views of the algorithms provide some very useful insights for beginning students. Chen's applets with accompanying explanations of the algorithms may be found at http://gaigs.cmsc.lawrence.edu/animation/.

Students of Myles McNally at Alma College have created a variety of interesting algorithm animations in Java. These include animations of linked lists, searching, sorts, and queues. They may be accessed at http://charis.mcs.alma.edu. The animations are accompanied by hypertext descriptive materials and links to additional sites.

Alejo Hausner of the CS Department at Princeton University at Princeton University has developed a collection of excellent animations of sorting and computational geometry algorithms. Many of these animations include three-dimensional views of the algorithms, and all of them are driven by an interface that offers the viewer a variety of controls. Hausner's work may be viewed at http://www.cs.princeton.edu/~ah/alg_anim/index.html.

Susan Rodger of Duke University has authored several Java visualizations of parsing algorithms. FLAP is a package of graphical tools which can be used as an aid in learning the basic concepts of Formal Languages and Automata Theory. Pâté is a program (unfortunately written as a Java application instead of a Web applet) which transforms context free grammars and parses restricted and unrestricted grammars. PumpLemma is a tool for experimenting with the Pumping Lemma for regular languages and context-free languages. These are accessed via her home page at http://www.cs.duke.edu/~rodger.

Michiel van de Panne of the University of Toronto has a marvelous collection of Java applets to illustrate concepts in computer graphics. Among the graphics algorithms for which van de Panne has developed applets are: 3D Translations and rotations; an interactive tutorial on cross-products; interactive illustration of L-systems; graphics tutorials on transformations, projections, curves, and surfaces; curve tutorial. The material may be accessed at http://www.dgp.toronto.edu/people/van/courses/csc418/.

Joe Bergin of Pace University has written a Java applet that provides animations of bubble, selection, and quick sorts with a variety of options for input generators. Bergin's work is at http://csis.pace.edu/~bergin/Java/applets.htm.

5 Complete visualization systems with automatic creation

These systems create the visualizations in a completely automatic fashion, transparent to the program code that implements the algorithm. Many of these systems include a variety of examples and demonstrations.

Rockford Ross's Dynalab system provides a very complete program animation system animation system for Pascal programs and also animations of programs written in subsets of Ada and C++. At the moment Ross only has a prototype of what the Web version of his system will look like. However, there's every indication that the entire Dynalab system will be ported to Java and the Web in the near future. Look at http://www.cs.montana.edu/~dynalab for details and the current status of Ross' project.

Ricardo Jiménez-Peris and Marta Patiño-Martínez of Universidad Politécnica de Madrid have a visual programing environment for Modula-2 programs that visualizes automatically recursion, dynamic memory, input/output, arrays, etc. It currently runs under DOS but they are working in adding a facility to generate traces that are interpreted by a Java applet, so a visualization of a particular run of a program can be introduce in a web page. A link to this project is http://lml.ls.fi.upm.es/VisualGroup/VisMod.html. A similar project for functional programming language is Visual Hipe [19] at the same university in which participate Ricardo Jiménez-Peris, Cristóbal Pareja-Flores, Marta Patiño-Martínez and Ángel Velázquez-Iturbide. In this environment the rewriting process uses a mixed textual/graphical notation, where structured values as trees and lists are represented graphically while functions and other constructors are shown textually. There are DOS and ms-windows versions and a similar facility as the one commented above is being added. This work is at http://lml.ls.fi.upm.es/VisualGroup/VisualHipe.html.

Jorma Tarhio's Jeliot offers a Java programming environment with animation hooks automatically built into the system. Web viewers of Jeliot can enter a Java program, Jeliot will then interpret and execute the program. Moreover, if the program uses the visualized data types provided by Jeliot, animation of the program will be automatic because the animation operations are embedded (transparently to the Java programmer) in the operations of the data types. Tarhio encourages interested surfers to check out Jeliot at http://www.cs.helsinki.fi/research/aaps/Jeliot.

6 Complete visualization systems requiring program annotation

These systems require that the designer of the animation make some form of annotations to program code. Many of these systems include a variety of examples and demonstrations.

Bertrand Ibrahim of the Computer Science Department, University of Geneva, has directed a project that allowed the surfer to control the execution of Pascal programs from within an HTML document. The approach used by Ibrahim's group is based on CGI scripting. The best description of the technique used appears on Ibrahim's Web pages http://medusa.acs.uci.edu/indiv/franklin/doc/ibrahim/abstract.html or http://cuisung.unige.ch/eao/www/WWW94/paper.html: "The solution we finally chose consists in having the shell script, invoked by the HTTP server, spawn a child process to run a slightly modified version of the Pascal program. The modification consists in adding, between each original Pascal instruction, a call to a synchronization procedure. The synchronization procedure checks whether the execution of the Pascal program should continue, or be interrupted. Whenever there is a breakpoint on the current instruction, or when the user has selected the single step button, the current state is sent to the client viewer, and the synchronization procedure waits for a signal from the server-activated shell script to resume execution, with possibly new breakpoints and selected variables, based on the latest user request."

Marc Brown of Digital Systems Research has developed a methodology for visualizing algorithms over the Web using the Visual Obliq programming language. Sample algorithms available for viewing at Brown's site include bin packing, selection sort and Dijkstra's shortest path algorithm. Unfortunately, although intended to be system-independent like Java, the Visual Obliq language currently will only execute programs under browsers such as DeckScape, WebCard, or WebScape that have also been developed at the same System Research Center. Although Brown states "We are currently investigating how to implement CAT (his system) using standard components, such as Java and ActiveX," the status of this once promising project is unclear since Brown recently left the DEC SRC group. Consult Brown's Web page at http://www.research.digital.com/SRC/webbrowsing/#oblets for more information.

John Stasko of Georgia Tech developed the XTango system to facilitate the animation of algorithms developed in Xwindows using the C programming language (see http://www.cc.gatech.edu/gvu/softviz/SoftViz.html). Steven Hartley of Drexel has recently ported a subset of XTango to Java. For documentation and sample illustrations, point your browser at http://www.mcs.drexel.edu:80/~shartley.

John Stasko's Samba system makes it possible to add animation to programs by simply adding to a program textual output statements in Samba's scripting language. The Samba script reader then reads from this textual script to produce the animation. The advantage of Samba, as opposed to XTango, is that the animator of the algorithm does not have to understand a detailed set of graphics function calls. Consequently, Stasko maintains that animating an algorithm becomes easy enough for undergraduates to do in a data structures and algorithms course [32]. Stasko has a "beta" version of Samba in Java available to test at his Web site http://www.cc.gatech.edu/gvu/softviz/SoftViz.html. One of the current drawbacks of the Java version of Samba is that the scripting commands for Samba in Java must be fed to the system in a Java text window because the security restrictions of Java do not allow reading from a local file.

Susan Rodger's JAWAA system at Duke is similar in principle to Stasko's Java version of Samba. That is, a Java applet reads commands from a textual scripting language to construct an animation of the algorithm. Rodger solves the file access problem cited above with respect to Stasko's Java version of Samba by directing the JAWAA applet to a URL that contains the JAWAA script. To find out more information about JAWAA, consult http://www.cs.duke.edu/~rodger.

Tom Naps' WebGAIGS portrays the actions of a variety of algorithms through a sequence of discrete snapshots of data structures that the algorithm manipulates. The surfer provides input to the algorithm through an HTML form that triggers a CGI script which runs the algorithm (on the server) for that set of input. The WebGAIGS system then computes a collection of graphic primitives that will ultimately depict the algorithm. These primitives, along with a Java applet that renders them and provides a viewing environment for the snapshots, are then transmitted to the Web client. The graphical snapshots are accompanied by explanatory text appearing in a HTML frame. To view the collection of algorithms currently depicted by this system, aim your browser at http://gaigs.cmsc.lawrence.edu.

The WWW-TRAKLA system developed by Ari Korhonen and Lauri Malmi at the Helsinki University of Technology is a Web-based, computer-aided learning environment for helping to teach algorithms and data structures. Not only does TRAKLA provide links to Java applets that portray a variety of algorithms, but it also distributes tracing exercises to the student and then evaluates the student's answers to the exercises. The student enters her answers to these exercises using an interactive graphical editor that is coded in the Java language. Korhonen and Malmi encourage interested parties to visit their pages at http://www.cs.hut.fi/~tred/WWW-TRAKLA/WWW-TRAKLA.html.

A Web-based visualization system soon to be made available by Dimitrios Theotokis of the University of Athens will offer student viewers of the visualization the opportunity to "customize" the version of the electronic book they are currently reading. Theokakis is exploring the use of JavaScript to achieve a high degree of interaction between the student, visual representations of algorithms, and accompanying textual materials. You can keep yourself posted on the progress of Theotokis's project by checking http://www.di.uoa.gr/~dtheo.

Web-based visualization tools for helping our students understand and explore computer science concepts are destined to be a medium that will evolve very fast. As such, any survey in a static document such as these proceedings is bound to be obsolete almost as soon as it is published. Consequently, let us offer at least two Web sites which will help keep you up to date on what is available. First, Scott Grissom of the University of Illinois at Springfield has started the Visualization Resource Center for Computer Science educators at http://www.uis.edu/~grissom/VRC. Grissom's VRC promotes the use and development of visualizations (not limiting itself to Web-based visualizations) to teach computer science. It is a peer-reviewed collection of tools, visualizations, demonstration ideas, references, and Internet resources. Authors wishing to submit their visualizations to Grissom's center may do so through forms available at the Web site. A second on-line resource for strictly Web-based visualization will be maintained by our own working group after the conclusion of this year's ITiCSE Conference. To access this site, point your browser at http://sol.pace.edu/webvis/. Anyone interested in contributing sites to be listed on this page should contact any member of our working group.


To submit materials to this repository, send a link and a description to the email address below.
Date created: Friday, June 13, 1997
Last modified: Wednesday, November 19, 1997
Copyright © 1997, Joseph Bergin
Maintained by: Joseph Bergin
berginf@pace.edu