Field Reports tell how instructors have used AVs in their teaching.

Data structures assignment on graphs in which students construct AV of deadlock detection algorithm

No replies
White BeltYellow BeltGreen BeltRed Belt
Joined: 2009-06-11
Points: 65
Tom Naps
University of Wisconsin - Oshkosh
Term / Date: 
Spring 2009
The AV engagement taxonomy specifies four active levels of learner engagement with AV — responding, changing, constructing, and presenting. In this field 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 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 first 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 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 identifiers, and the resources are represented by blue graph nodes with lower-case letters for identifiers. 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 Students must complete the deadlock_exists and color_cycle_red methods in the 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