Build an Algorithm Animation with Polka

Problem
Software visualization systems present symbolic, graphical depictions of computer programs to help people understand how the programs work. In this assignment, you will use the Polka system to develop an animation of a computer program or algorithm. Polka is written in C++ and requires you to code in that language. You don't have to be a C++ expert, but you should have had some experience with the language. We do have a new Java version of Polka (called Rumba) that is not as well tested, but that is available for use as an alternative platform.

Polka supports color, 2-D animations of programs. The animation can be run in parallel with its driving program (on-line), or the animation driven from a trace file post-mortem to the program's execution. The support environment for Polka is the X11 Window system and Motif running on Sun SPARCstation workstations. We also may have a Windows '95 native version available too. Please ask about that if you are interested.

To learn more about Polka and to understand its animation paradigm, the following reference will be essential: " A Methodology for Building Application-Specific Visualizations of Parallel Programs," GVU Technical Report Number GIT-GVU-92-10, June 1992. Also needed for this assignment is a copy of the documentation for the Polka library and toolkit. This document is available at /net/ag20/softviz/polka/Doc/polkadoc.ps. (A lite version, polkadoc-lite.ps, exists there as well.)

To experiment with the Polka system, log into a Sun workstation and start up X. The important directory for the system is /net/ag13/projects/polka. Pertinent subdirectories for animations are Anims and Anims/Parallel. Both of these directories contains many sample animations that will be extremely valuable and helpful to you as you learn the system. In particular, the animation ``tutorial'' in the Anims directory, shows off lots of the neat Polka features and how to implement them. To run one of the animations there, do the following:

1. Change to the appropriate subdirectory.
2. Run any executable there such as tutorial, hanoi, bpack, knight, mst, balls, etc. In the Parallel subdirectory, interesting animations are mst, psortn, msort, kiviat, feynman, etc. Note that a number of the animations require the use of an input file. So if the executable is foo, you may have to run it via
   % foo < foo.in
3. If the animation that you want to see has not been compiled, make a directory under your home directory, and copy over the appropriate files from the anims directory. The files you need will be the Makefile and the files foo.C, fooscenes.C, foo.H, and foo.in assuming that "foo" is the name of the program. To compile, give the command "make PROG=foo." IMPORTANT: Make sure that the C++ compiler you are using is /usr/local/lang/CC. You will have problems otherwise.

You will need to understand the animation paradigm used in Polka to build your animation. The references described earlier should help you in this regard. The paradigm has been designed especially to promote ease-of-use, and it requires no substantive graphics background. Your animation needs to include the file polka.H from the polka directory and bind in the library polka.o into your executable.

Background
Link to more information on this research area.

Deliverables
For this assignment, you should turn in the following items:

• The absolute paths to your program code and your animation code. Make sure these files are readable!
• A 3-5 page report that briefly describes the algorithm you chose, and then discusses the animation design choices you made. Why did you illustrate the program in the manner that you did?

Evaluation
Evaluation will be partially based on the quality and richness of your animation. How well does it illustrate the algorithm? The other part of the evaluation will be based on your written report, how well you convey what you did and why you did it.