1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<!-- <base href = "http://localhost/~ckhung/"> -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta name="generator"
content="HTML Tidy for Linux/x86 (vers 1st March 2003), see www.w3.org" />
<?php include "../../i/meta.en.php" ?>
<title>User Guide for Algotutor</title>
</head>
<body>
<?php include "header.en.php" ?>
<div id="content">
<h1>User Guide for Algotutor</h1>
<hr />
<h2>What is Algotutor?</h2>
<p><code class="lit">algotutor</code> 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.</p>
<p>Home page of algotutor is at:
<a href="http://people.ofset.org/~ckhung/p/algotutor/">
http://people.ofset.org/~ckhung/p/algotutor/</a>
; current version is 0.8.6, released Apr 9, 2007.</p>
<h2>Prerequisite</h2>
<ul>
<li>dependency: This program requires
<a href="http://www.perltk.org/">perl-Tk</a>.</li>
<li>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.</li>
<li>Hardware: Being a script, algotutor runs very slowly on old
machines.</li>
</ul>
<h2><a id="dl" name="dl"></a>Downloading and Installing
<code class="lit">algotutor</code></h2>
<p>Whatever OS you use, please install
<a href="http://www.perltk.org/">perl-Tk</a> first. It is also
available in several package formats, for example as .deb or as
<a href="http://rpmfind.net/linux/RPM/">.rpm</a></p>
<p>Debian users can download the latest algotutor_0.*_all.deb from
<a href="http://debian.ofset.org/dists/sarge/main/binary-all/">the
debian archive at OFSET</a>. If you would like to do: <code>apt-get
install algotutor</code>, please add the following lines to the file
/etc/apt/sources.list :</p>
<pre class="code">
deb http://debian.ofset.org/ sarge main
deb-src http://debian.ofset.org/ sarge main
</pre>
<p>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 <code>rpm -U --nodeps
algotutor-*.rpm</code> as long as perl-Tk is indeed installed.</p>
<p>There is also a
<a href="http://www.freebsd.org/cgi/cvsweb.cgi/ports/math/algotutor/">
FreeBSD port</a> and a possibly outdated
<a href="http://www.openbsd.org/cgi-bin/cvsweb/ports/education/algotutor/">
OpenBSD port</a>.</p>
<p>Users of other operating systems can download
<a href="../../dl/algotutor-0.8.6.tgz">the source</a> (md5sum:
see web page), extract the files, and run it
directly. No compilation is required since it is written in perl. For
MS Windows users, the
<a href="http://xlivecd.indiana.edu/">XLiveCD</a> environment is
recommended but perhaps not required. It is a variant of
<a href="http://sources.redhat.com/cygwin/">cygwin</a> that does not
require installation. Once the source file is downloaded, just do:</p>
<ol>
<li><code>tar xzf
<em>/path/to/</em>algotutor-<em>version</em>.tgz</code> Of course
<em>/path/to/</em> and <em>version</em> 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
<code>d:\download\abc.tgz</code>, you need to access it from the
bash command line prompt as
<code>/cygdrive/d/download/abc.tgz</code>.</li>
<li><code>cd algotutor-<em>version</em></code></li>
<li><code>cat Makefile</code></li>
</ol>
<p>Now you can cut the <code>./algotutor -a ...</code> commands in
the Makefile and paste them into the terminal window and see how it
works.</p>
<p>Also, <code class="lit">algotutor</code> has been submitted for
inclusion in the upcoming freeduc-cd-science 1.5.
<a href="http://www.ofset.org/freeduc-cd">freeduc-cd</a> 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.</p>
<p>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!</p>
<h2>Running <code class="lit">algotutor</code></h2>
<p>Let's see an example to begin with:<br />
<code>algotutor -a bst</code>
<code class="id">/full/path/to/</code><code>countries.gr</code><br />
This command reads the data and operations in the file
<code>countries.gr</code>, constructs a binary search tree, and
performs the specified operations on it. Of course you need to
replace <code class="id">/full/path/to/</code> with the true path of
your data file.</p>
<p>Sometimes one may want to specify which step to display
initially, dump the picture as a postscript file, and exit
immediately:<br />
<code>algotutor -a rbt -i 75 -d red-black-tree.ps data/countries.gr</code><br />
This can be useful for example if you want to invoke algotutor from
WIMS.</p>
<p>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:</p>
<ul>
<li>(debian, knoppix, ...) <code>dpkg -L algotutor | grep
'\.gr\>'</code></li>
<li>(mandrake, redhat, ...) <code>rpm -ql algotutor | grep
'\.gr\>'</code></li>
<li>(slackware) <code>grep '\.gr\>'
/var/log/packages/algotutor*</code></li>
</ul>
<p>The list of available algorithms (that is, what can be put after
<code>-a</code>) is found in the <a href="algotutor.php">manual
page</a>. Here are a few examples, assuming that you give the
commands at the data directory:</p>
<pre class="code">
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
</pre>
<p>The dynamic programming algorithms do not require data files.
Input data are specified directly as command line arguments:</p>
<pre class="code">
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
</pre>
<p>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 <code>perl algotutor -a graham
data/pts1.gr</code>.</p>
<p>Not all algorithms can be performed on all data files. (... -type
...)</p>
<p>Some algorithms use auxiliary data structures. Such data
structures are displayed in a separate canvas. For example:<br />
<code>algotutor -a dijk</code>
<code class="id">/full/path/to/</code><code>randgrid.gr</code><br />
This runs Dijkstra's single-source shortest path algorithm on the
graph file <code>randgrid.gr</code>. In this algorithm, the set of
<em>fringe nodes</em> are stored in a heap. So there is a separate
canvas for that heap.</p>
<h2>Creating Your Own Data Files</h2>
<p>For Heap, BST, and Red-Black Tree algorithms, please see
countries.gr for an example.</p>
<p>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.</p>
<p>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 <code>-compare</code> to choose a different comparison
key.</p>
<h2>Customizing the Appearance of the Vertices, etc.</h2>
<p>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:
<code>$::Config->{...} = ...</code> The config system is not yet
mature and is subject to major changes in the future.</p>
<h2>Using gen_at_graph to generate random graphs</h2>
<p><a href="gen_at_graph.php">manual page for gen_at_graph</a></p>
<hr />
<ul>
<li>return to <a href=".">algotutor home page</a></li>
</ul>
<?php include "footer.php" ?>
</div>
<?php include "$top[fs]/i/navigator.en.php" ?>
</body>
</html>
|
