University of Wisconsin - Oshkosh
engagement taxonomy speciﬁes four active levels of learner engagement with AV
— responding, changing, constructing, and presenting. In this ﬁeld report I describe a programming assignment for a data structures course that has students construct an algorithm visualization of an algorithm to detect a cycle within a graph. Students use the GAIGSGraph, VisualGraph, and VisualNode classes in the JHAVE
/Gaigs data structure library that was developed by Myles McNally of Alma College. See http://jhave.org/developer/doc/index.html
for the javadocs that detail classes and methods in this library. Because they are working with a graph class that knows how to “draw itself” in JHAVE
when a writeSnap method is called, visualizing their program is nearly as easy as inserting tracing print statements when debugging. In the context of constructing AV
, they are drawing a picture of the state of the algorithm at its “interesting events”.
To set the stage for the assignment we ﬁrst describe a classic operating systems problem — deadlock detection. A particular scenario to which their program is subjected can be described in terms of a resource allocation graph. The image at http://jhave.org/algo_viz_ﬁeld_reports/deadlock.png
shows an example of such a resource allocation graph produced by a student’s program. Here the processes are represented by yellow graph nodes with capital letters for identiﬁers, and the resources are represented by blue graph nodes with lower-case letters for identiﬁers. An arrow from a resource to a process indicates that the resource is owned by a particular process. An arrow from a process to a resource indicates that a process has requested a particular resource. Deadlock exists when there is a cycle in this graph.
Students are given a code base to start from. To complete the assignment, they must use the GAIGSgraph class to (1) detect when deadlock exists and then (2) color red the edges in the cycle underlying that deadlock. That code base, complete with an ant build script can be downloaded from http://jhave.org/algo_viz_ﬁeld_reports/deadlock.zip
. Students must complete the deadlock_exists and color_cycle_red methods in the Deadlock.java program. To compile the program, use “ant compile”. To run the program use “ant run”. Finally, to view the visualization that is produced (and see whether they have correctly solved the problem), use “ant view” to load the visualization script foo.sho into the JHAVE
client running in local debug mode.
Questions from anyone wanting to use or know more about this assignment should be directed to Tom Naps at firstname.lastname@example.org