User Guide for Algotutor

What is Algotutor?

algotutor is an interactive program for observing the intermediate steps of algorithms ("algorithm animation"). The target audience is computer science students and/or anyone who studies algorithms and/or data structures. One can create data files in plain text format (actually perl anonymous hashes, but one need not care) and let algotutor runs through some predefined algorithm. Then one can step backward and forward through the execution sequence of the algorithm at different levels of details.

Home page of algotutor is at: http://people.ofset.org/~ckhung/p/algotutor/ ; current version is 0.8.6, released Apr 9, 2007.

Prerequisite

dependency: This program requires perl-Tk.
OS: I believe it can run almost everywhere perl-Tk can, including for example *BSD. It has been developed on Mandrake tested on several flavors of GNU/Linux, and reported to work on various flavors of MS Windows.
Hardware: Being a script, algotutor runs very slowly on old machines.

Downloading and Installing `algotutor`

Whatever OS you use, please install perl-Tk first. It is also available in several package formats, for example as .deb or as .rpm

Debian users can download the latest algotutor_0.*_all.deb from the debian archive at OFSET. If you would like to do: apt-get install algotutor, please add the following lines to the file /etc/apt/sources.list :

	deb http://debian.ofset.org/ etch main
	deb-src http://debian.ofset.org/ etch main

(Replace "etch" by "sarge" if your Debian is old.)

Users of RPM based distributions can download the latest algotutor-0.*.noarch.rpm from the same directory. It is generated from the debian package by alien and has some unnecessary dependency. You can safely force no dependency check by rpm -U --nodeps algotutor-*.rpm as long as perl-Tk is indeed installed.

There is also a FreeBSD port and a possibly outdated OpenBSD port.

Users of other operating systems can download the source (md5sum: 58b867cb319ed3e6f8b0bd434b4d9145), extract the files, and run it directly. No compilation is required since it is written in perl. For MS Windows users, the XLiveCD environment is recommended but perhaps not required. It is a variant of cygwin that does not require installation. Once the source file is downloaded, just do:

tar xzf /path/to/algotutor-version.tgz Of course /path/to/ and version has to be replaced with the true path and version number of your downloaded file. Note to cygwin users: Say you have a file at d:\download\abc.tgz, you need to access it from the bash command line prompt as /cygdrive/d/download/abc.tgz.
cd algotutor-version
cat Makefile

Now you can cut the ./algotutor -a ... commands in the Makefile and paste them into the terminal window and see how it works.

Also, algotutor has been submitted for inclusion in the upcoming freeduc-cd-science 1.5. freeduc-cd is a live CD based on knoppix full of education software that you can use on any cd-bootable computer without installation hassle. The drawback is that it is not release as often as the source or as the binary packages and therefore may contain an older version of algotutor.

The debian and rpm packages are provided courtesy of Georges Khaznadar of the freeduc-cd fame. The OpenBSD port and the FreeBSD port are kindly provided by Kevin Lo. Many thanks to Georges and Kevin!

Running `algotutor`

Let's see an example to begin with:
algotutor -a bst /full/path/to/countries.gr
This command reads the data and operations in the file countries.gr, constructs a binary search tree, and performs the specified operations on it. Of course you need to replace /full/path/to/ with the true path of your data file.

Sometimes one may want to specify which step to display initially, dump the picture as a postscript file, and exit immediately:
algotutor -a rbt -i 75 -d red-black-tree.ps data/countries.gr
This can be useful for example if you want to invoke algotutor from WIMS. The number after -i must be >= 0 and < n where n is the total number of marks as printed by algotutor.

algotutor comes with a few sample data files. Depending on the distribution you are using, you can use one of the following commands to see where the data files are installed:

(debian, knoppix, ...) dpkg -L algotutor | grep '\.gr\>'
(mandrake, redhat, ...) rpm -ql algotutor | grep '\.gr\>'
(slackware) grep '\.gr\>' /var/log/packages/algotutor*

The list of available algorithms (that is, what can be put after -a) is found in the manual page. Here are a few examples, assuming that you give the commands at the data directory:

        algotutor -a graham data/pts1.gr
        algotutor -a dom data/pts1.gr
        algotutor -a heap data/countries.gr
        algotutor -a bst data/countries.gr
        algotutor -a rbt data/countries.gr
	algotutor -a dfs data/trc.gr
	algotutor -a dfsv data/trc.gr
        algotutor -a prim data/randgrid.gr
        algotutor -a dijk data/tt.gr
        algotutor -a flwa data/lv.gr

The dynamic programming algorithms do not require data files. Input data are specified directly as command line arguments:

        algotutor -a lcs AGCTATACGATGACT GTCAGTATAGTCATATG
        algotutor -a matc 32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35

In an MS Windows environment without cygwin, one has to run these commands from the command line window "cmd", and prefix each command with "perl", such as perl algotutor -a graham data/pts1.gr.

Not all algorithms can be performed on all data files. (... -type ...)

Some algorithms use auxiliary data structures. Such data structures are displayed in a separate canvas. For example:
algotutor -a dijk /full/path/to/randgrid.gr
This runs Dijkstra's single-source shortest path algorithm on the graph file randgrid.gr. In this algorithm, the set of fringe nodes are stored in a heap. So there is a separate canvas for that heap.

Creating Your Own Data Files

For Heap, BST, and Red-Black Tree algorithms, please see countries.gr for an example.

For Graph algorithms, please see tt.gr for an example. The asymmetry between ftw-ama and ama-ftw edge pair is intentional. It serves to verify that bad input does not crash algotutor.

Since the data file is actually a perl script, you can do a lot of fun things with the data file. For example, you can change the definition of -compare to choose a different comparison key.

Customizing the Appearance of the Vertices, etc.

One can customize the appearance of the vertices, etc. by creating either a personal config file ~/.algotutor or a system-wide config file /etc/algotutor . A sample config file is provided in the source package as etc/algotutor . For more configuration possibilities, please search the source code *.pm for such statements: $::Config->{...} = ... The config system is not yet mature and is subject to major changes in the future.

Using gen_at_graph to generate random graphs

manual page for gen_at_graph

return to algotutor home page