Narrative algorithm visualization

ABSTRACT

Visualization of algorithms has been shown to be a useful aid for educational purposes. In this work we focus on the creation of algorithm visualizations based on viewing the visualization as a narrative. This view promotes the creator to form a central plot and define abstract participating players. Following this view, the basic elements defining a visualization, namely visual metaphors and temporal transitions - are naturally addressed. The players which signify abstract notions in the algorithm define the depictions, and the story defines the transition over time. This encourages the creator to focus on the mapping process that is the basis of any visual depiction, and helps create a more engaging visualization. We present a study comparing two visualizations, a narrative one and a non-narrative one that supports the effectiveness of the narrative approach.

References

1. Baker, J. E., Cruz, I. F., Liotta, G., and Tamassia, R. 1996. Algorithm animation over the World Wide Web. In Proceedings of the workshop on Advanced visual interfaces, ACM Special Interest Group on Multimedia, 203--212.
2. Beall, J. E., Doppelt, A. M., and Hughes, J. F. 1996. Developing an interactive illustration: Using java and the web to make it worthwhile. In Proceedings of Computer Graphics Proceedings of 3D and Multimedia on the Internet, WWW and Networks.
3. Bertin, J. 1983. Semiology of Graphics. University of Wisconsin Press.
4. Blelloch, G. E. 1995. NESL: A Nested Data-Parallel Language (Version 3.1). Tech. Rep. CMU-CS-95-170, Carnegie Mellon University, Pittsburgh, PA.
5. Blumenkrants, M., Starovisky, H., and Shamir, A., 2005. Graph algorithm visualization. www.faculty.idc.ac.il/arik/GraphAA/graphAlgorithms.html.
6. Blumenkrants, M., Starovisky, H., and Shamir, A., 2005. Recursive fill visualization. www.faculty.idc.ac.il/arik/GraphAA/fillAlgorithms.html.
7. Brown, M. H., and Najork, M. A. 1996. Collaborative active textbook: a web-based algorithm animation system for an electronic classroom. IEEE Symposium on Visual Languages, 266--275.
8. Brown, M. H., and Sedgewick, R. 1984. A system for algorithm animation. In SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, 177--186.
9. Brown, M. H. 1988. Perspectives on algorithm animation. In CHI '88: Proceedings of the SIGCHI conference on Human factors in computing systems, ACM Press, New York, NY, USA, 33--38.
10. Brown, M. H. 1991. Zeus: A system for algorithm animation and multi-view editing. In Proceedings of the 1991 IEEE Workshop on Visual Languages, 4--9.
11. Byrne, M., Catrambone, R., and Stasko, J. T. 1999. Evaluating animations as student aids in learning computer algorithms. Computers&Education 33, 253--278.
12. Colombo, B. A., Demetrescu, C., Finocchi, I., and Laura, L. 2003. A system for building animated presentations over the Web. In the AICCSA'03 Workshop on Practice and Experience with Java Programming in Education, IEEE.
13. Demetrescu, C., and Finocchi, I. 1999. A general-purpose logic-based visualization framework. In Proceedings of the 7th International Conference in Central Europe on Computer Graphics, Visualization and Interactive Digital Media, 55--62.
14. Gershon, N., and Page, W. 2001. What storytelling can do for information visualization. Communications of the ACM 44, 8, 31--37.
15. Gibly, S., and Shamir, A., 2006. Graph algorithms applet. www.faculty.idc.ac.il/arik/GraphAA/GraphApplet/GraphApplet.html.
16. Hamilton-Taylor, A. G., and Kraemer, E. 2002. Ska: supporting algorithm and data structure discussion. In SIGCSE: ACM Special Interest Group on Computer Science Education, ACM Press, New York, 58--62.
17. Hansen, S., Narayanan, H. N., and Hegarty, M. 2002. Designing educationally effective algorithm visualizations. Journal of Visual Languages and Computing 13, 3, 291--317.
18. Hübscher-Younger, T., and Narayanan, N. H. 2003. Dancing hamsters and marble statues: characterizing student visualizations of algorithms. In SoftVis '03: Proceedings of the 2003 ACM symposium on Software visualization, ACM Press, New York, NY, USA, 95--104.
19. Hundhausen, C. D., and Douglas, S. 2000. Using visualizations to learn algorithms: should student construct their own, or view an expert's? In IEEE Annual Symposium on Visual Languages, Los Alamitos, California, IEEE, 21--28.
20. Hundhausen, C., Douglas, S., and Stasko, J. T. 2002. A meta-study of algorithm visualization effectiveness. Journal of Visual Languages and Computing 13, 3 (June), 259--290.
21. Hundhausen, C. D., Patterson, R., Brown, J. L., and Farley, S. 2004. The effects of algorithm visualizations with storylines on retention: An experimental study. In 2004 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2004), IEEE Computer Society, Rome, Italy, 226--228.
22. Hundhausen, C. D. 1998. Toward effective algorithm visualization artifacts: designing for participation and negotiation in an undergraduate algorithms courses. In Conference on Human Factors in Computing Systems, ACM Press, 54--55.
23. Kehoe, C., Stasko, J. T., and Tayloe, A. 2001. Rethinking the evaluation of algorithm animations as learning aids: An observational study. International Journal of Human Computer Studies 54, 2 (February), 265 -- 284.
24. Lawrence, A., Badre, A., and Stasko, J. T. 1994. Empirically evaluating the use of animations to teach algorithms. In Proceedings of the 1994 IEEE Symposium on Visual Languages, St. Louis, MO, 48--54.
25. Lewalter, D. 2003. Cognitive strategies for learning from static and dynamic visuals. Learning and Instruction 13, 177--189.
26. Mayer, R. E., and Anderson, R. B. 1991. Animations need narration: An experimental test of a dual-coding hypothesis. Journal of Educational Psychology 83(4), 484--490.
27. Mayer, R. E., and Sims, V. K. 1994. For whom is a picture worth a thousand words? extensions of a dual-coding theory of multimedia learning. Journal of Educational Psychology 86, 389--401.
28. Najork, M. A., and Brown, M. H. 2001. Three-dimensional web-based algorithm animations. Tech. Rep. SRC Research Report 170, Compaq Systems Research Center, Palo Alto.
29. Najork, M. A. 2001. Web-based algorithm animation. In 38th Design Automation Conference, ACM Press, 506--511.
30. Naps, T. L., Eagan, J. R., and Norton, L. L. 2000. JhavÉ an environment to actively engage students in web-based algorithm visualizations. In SIGCSE '00: Proceedings of the thirty-first SIGCSE technical symposium on Computer science education, ACM Press, New York, NY, USA, 109--113.
31. Naps, T. L., Rossling, G., Almstrum, V., Dann, W., Fleischer, R., Hundhausen, C. D., Korhonen, A., Malmi, L., McNally, M., Rodger, S., and Velázquez-Iturbide, J. A. 2002. Exploring the role of visualization and engagement in computer science education. SIGCSE Bulletin 35, 2, 131--152.
32. Paivio, A. 1990. Mental representations: a dual coding approach. Oxford University Press.
33. Pierson, W. C., and Rodger, S. H. 1998. Web-based animation of data structures using JAWAA. In the 29th SIGCSE Technical Symposium on Computer Science Education, ACM Press, New York, 267--271.
34. Robledo, G. 2002. Words without meaning. MCTM Bulletin XXVII, 6 (October), 1.
35. Rodger, S. H. 2002. Introducing computer science through animation and virtual worlds. In 33rd SIGCSE Technical Symposium on Computer Science Education, 186--190.
36. Rössling, G., Schüer, M., and Freisleben, B. 2000. The ANIMAL algorithm animation tool. In The 5th Annual ACM SIGCSE/SIGCUE Conference on Innovation and Technology in Computer Science Education, ACM Press, New York, 37--40.
37. Saraiya, P. 2002. Effective Features of Algorithm Visualizations. Master's thesis, Virginia Polytechnic Institute and State University.
38. Scaife, M., and Rogers, Y. 1996. External cognition: how do graphical representations work? International Journal of Human-Computer Studies 45, 2 (August), 185--213.
39. Sedgewick, R. 1989. Algorithms. Addison-Wesley, Reading, MA.
40. Shneerson, M., and Tal, A. 1997. Gasp-2: A geometric algorithm animation system for am electronic classroom. In Gasp-2: A Geometric Algorithm Animation System for am Electronic Classroom, ACM Press, New York, Annual Symposium on Computational Geometry, 379--381.
41. Stasko, J. T., and Hundhausen, C. D. 2004. Algorithm visualization. In Computer Science Education Research, S. Fincher and M. Petre, Eds. Routledge Falmer, London, 199--228.
42. Stasko, J. T., Badre, A., and Lewis, C. 1993. Do algorithm animations assist learning? an empirical study and analysis. In Proceedings of ACM INTERCHI 1993 conference of human factors in computing systems, 61--66.
43. Stasko, J. T. 1990. Tango: A framework and system for algorithm animation. IEEE Computer Society Press 23, 9, 27--39.
44. Tal, A., and Dobkin, D. 1995. Visualization of geometric algorithms. IEEE Transactions on Visualization and Computer Graphics 1, 2, 194--204.
45. Tudoreanu, M. E. 2003. Designing effective program visualization tools for reducing user's cognitive effort. In Proceedings of the 2003 ACM symposium on Software visualization, ACM Press, New York, USA, 105--114.
46. Wiggins, M. 1998. An overview of program visualization tools and systems. In the 36th ACM annual Southeast regional conference, ACM Press, New York, 194--200.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

  • Modeling and simulation

    • Simulation types and techniques

      • Simulation by animation