Programming Assignment 4 - Algorithm Animation

Due Date

See the assignment turn-in page (last modified on 22 September 2009) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 4 is Friday, 18 December at 11: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-305-503/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 tree algorithms or problems described in the text, implement it, and annotate it with print statements that produce an animation of the implementation’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 tree and randomly select the target node.

Output

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