Programming Assignment 4 - Algorithm Animation

Due Date

See the assignment turn-in page (last modified on 16 October 2007) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 4 is Monday, 15 December at 5:30 p.m.. It is not possible to turn-in Assignment 4 after the absolute deadline.

Background

Samba is an anamation system that reads drawing commands from std-in, executes them, and displays the result in a window.

The file samba.txt in the assignment directory /export/home/class/cs-306/a4 contains the Samba documentation. The Samba executable samba is in the same directory. The tar file samba.tar.bz2 in the same directory contains the source for Samba (and Polka, on which Samba is built) if you want to build Samba locally. There is a version of Samba that runs on Microsoft systems, but it's old (1997 vintage).

The Problem

Select one of the graph algorithms we discussed in class, implement it, and annotate it with print statements that produce an animation of the algorithm's execution when run through Samba. E-mail me (rclayton@monmouth.edu) your choice of algorithm so I can make sure there are no duplicates; algorithm selection is first-come, first-serve.

Input

To keep things simple, your program should generate problem instances internally without need for any input. For example, a depth-first search program would generate a graph and randomly select the start and target nodes.

For your convenience, there is some graph-generating code in the assignment directory; see the file gen-graph.h for details. The program draw-graph.cc in the same directory is a simple example of using gen-graph() and generating Samba commands.

Output

Your program should write to std-out Samba commands that animate its execution on the generated problem instance.