Algorithm animation over the World Wide Web

ABSTRACT

In this paper we propose a new model, called Mocha, for providing algorithm animation over the World Wide Web. Mocha is a distributed model with a client-server architecture that optimally partitions the software components of a typical algorithm animation system, and leverages the power of the Java language, an emerging standard for distributing interactive platform-independent applications across the Web.Mocha provides high levels of security, protects the algorithm code, places a light communication load on the Internet, and allows users with limited computing resources to access animations of computationally expensive algorithms. The user interface combines fast responsiveness and user friendliness with the powerful authoring capabilities of hypertext narratives.We describe the architecture of Mocha and show its advantages over previous methods for algorithm animation over the Internet. We also present a prototype of an animation system for geometric algorithms that can be accessed by any user with a WWW browser supporting Java (currently Netscape 2.0 and HotJava) at URL http://www.cs.brown.edu/people/jib/Mocha.html.

REFERENCES

• 1: Hotjava, 1995. http://www.javasoft.com/hotjava.html.
• 2: Netscape, 1995. http://home.netscape.com/comprod/products/navigator/version_2.0/.
• 3: James E. Baker , Isabel F. Cruz , Giuseppe Liotta , Roberto Tamassia, The Mocha algorithm animation system, Proceedings of the workshop on Advanced visual interfaces, May 27-29, 1996, Gubbio, Italy [doi>10.1145/948449.948487]
• 4: Tim Berners-Lee , Robert Cailliau , Ari Luotonen , Henrik Frystyk Nielsen , Arthur Secret, The World-Wide Web, Communications of the ACM, v.37 n.8, p.76-82, Aug. 1994 [doi>10.1145/179606.179671]
• 5: Prosenjit Bose , Giuseppe Di Battista , William Lenhart , Giuseppe Liotta, Proximity Constraints and Representable Trees, Proceedings of the DIMACS International Workshop on Graph Drawing, p.340-351, October 10-12, 1994
• 6: P. Bose, W. Lenhart, and G. Liotta. Characterizing proximity trees. Algorithmica. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia, to appear).
• 7: Marc Brown , John Domingue , Blaine Price , John Stasko, Software visualization, Conference companion on Human factors in computing systems, p.463, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/259963.260479]
• 8: M. H. Brown. Algorithm Animation. MIT Press, Cambridge, 1988.
• 9: M. H. Brown. ZEUS: A System for Algorithm Animation and Multi-View Editing. In IEEE Symposium on Visual Languages (VL '91), pages 4--9, 1992. Also available from http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-075.html.
• 10: Marc H. Brown , John Hershberger, Color and Sound in Algorithm Animation, Computer, v.25 n.12, p.52-63, December 1992 [doi>10.1109/2.179117]
• 11: Marc H. Brown , Marc A. Najork, Algorithm animation using 3D interactive graphics, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.93-100, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168651]
• 12: M. H. Brown and R. Sedgewick. Techniques for algorithm animation. IEEE Software, 2(1):28--39, 1985.
• 13: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, v.4 n.5, p.235-282, Oct. 1994 [doi>10.1016/0925-7721(94)00014-X]
• 14: Giuseppe Di Battista , William Lenhart , Giuseppe Liotta, Proximity Drawability: a Survey, Proceedings of the DIMACS International Workshop on Graph Drawing, p.328-339, October 10-12, 1994
• 15: John Domingue , Blaine Price , Marc Eisenstadt, A framework for describing and implementing software visualization systems, Proceedings of the conference on Graphics interface '92, p.53-60, September 1992, Vancouver, British Columbia, Canada
• 16: K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259--278, 1969.
• 17: E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns. Addison Wesley, 1995.
• 18: S. C. Glassman. A Turbo Environment for Producing Algorithm Animation. In IEEE Symposium on Visual Languages (VL '93), pages 32--36, 1993.
• 19: J. Gosling and H. McGilton. The Java language environment: a white paper, 1995. http://www.javasoft.com/whitePaper/java-whitepaper-1.html.
• 20: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 21: Scott E. Hudson , John T. Stasko, Animation support in a user interface toolkit: flexible, robust, and reusable abstractions, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.57-67, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168648]
• 22: J. W. Jaromczyk and G. T. Toussaint. Relative neighborhood graphs and their relatives. Proc. IEEE, 80(9):1502--1517, Sept. 1992.
• 23: D. G. Kirkpatrick and J. D. Radke. A framework for computational morphology. In G. T. Toussaint, editor, Computational Geometry, pages 217--248. North-Holland, 1985.
• 24: F. Manola. MetaObject protocol concepts for a RISC object model. Technical Report 0244-12-93-165, GTE Laboratories, Inc., December 1993.
• 25: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
• 26: J. Muthukumarasamy and J. T. Stasko. Visualizing Program Executions on Large Data Sets Using Semantic Zooming. Technical Report GIT-GVU-95-02, Georgia Institute of Technology, 1995.
• 27: B. Myers. Taxonomies of visual programming and program visualization. J. of Visual Languages and Computating, 1(1):97--123, March 1990.
• 28: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 29: Steven P. Reiss, Program Visualization: Where We Go From Here, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.218-227, September 07-11, 1992
• 30: S. P. Reiss. A Framework for Abstract 3D Visualizations. In IEEE Symposium on Visual Languages (VL '93), pages 100--107, 1993.
• 31: S. P. Reiss and I. F. Cruz. Practical Software Visualization. In CHI '94 Workshop on Software Visualization, 1994.
• 32: George G. Robertson , Stuart K. Card , Jack D. Mackinlay, Information visualization using 3D interactive animation, Communications of the ACM, v.36 n.4, p.57-71, April 1993 [doi>10.1145/255950.153577]
• 33: Robert W. Scheifler , Jim Gettys, The X window system, ACM Transactions on Graphics (TOG), v.5 n.2, p.79-109, April 1986 [doi>10.1145/22949.24053]
• 34: John Stasko , Albert Badre , Clayton Lewis, Do algorithm animations assist learning?: an empirical study and analysis, Proceedings of the SIGCHI conference on Human factors in computing systems, p.61-66, April 24-29, 1993, Amsterdam, The Netherlands [doi>10.1145/169059.169078]
• 35: J. T. Stasko. The path-transition paradigm: a practical methodology for adding animation to program interfaces. J. of Visual Languages and Computing, 1(3):213--236, 1990.
• 36: J. T. Stasko. Simplifying algorithm animation with tango. In Proc. IEEE Workshop on Visual Languages, pages 1--6, 1990.
• 37: John T. Stasko, Tango: A Framework and System for Algorithm Animation, Computer, v.23 n.9, p.27-39, September 1990 [doi>10.1109/2.58216]
• 38: Ayellet Tal , David Dobkin, GASP: a system to facilitate animating geometric algorithms, Proceedings of the tenth annual symposium on Computational geometry, p.388-389, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178100]
• 39: Ayellet Tal , David Dobkin, Visualization of Geometric Algorithms, IEEE Transactions on Visualization and Computer Graphics, v.1 n.2, p.194-204, June 1995 [doi>10.1109/2945.468401]
• 40: G. T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern Recogn., 12:261--268, 1980.
• 41: Andries van Dam, The electronic classroom: workstations for teaching, International Journal of Man-Machine Studies, v.21 n.4, p.353-363, Oct. 1984 [doi>10.1016/S0020-7373(84)80053-X]