[comp.edu] Algorithm animations

alistair@minster.york.ac.uk (06/13/89)

I would like to use animations of algorithms (searches, sorts, tree-building and traversal
etc) in an undergraduate course. Does anyone know of any software available to
do this - before I set out and re-invent the wheel?

Alistair Edwards		| Janet: alistair@uk.ac.york.minster
Department of Computer Science	| phone: (UK) (0904) 4327755
University of York		|	(international) +44 904 43277
Heslington, York		|
England YO1 5DD			|

siegman@sierra.Stanford.EDU (Anthony E. Siegman) (06/14/89)

There's a neat little sort demo for the Macintosh (you surely wouldn't
use any other machine, would you!) in the info-mac archives
(info-mac@sumex-aim at Stanford, anaonymous ftp), and I have seen tree
demos for the Mac also.  I'd try looking in the floppies or CD-ROMs
from Boston Computer Society (BCS), Berkeley Macintosh Users Group (or
is it Bay Area? -- BMUG, anyway), Educorp, Educomp, and Kinkos.

There is a book on ALGORITHM ANIMATION by Marc H. Brown, ISBN 02278-8
(1988) -- I have a catalog page about it, which doesn't name the
publisher, and I don't remember who it is.  It's an "ACM Distinguished
Dissertation" winner.

Writing to Professor Bob Eustis, School of Engineering, Stanford
University, Stanford  CA  94305 might get you some information about
other algorithm animation efforts under way here.

maner@bgsuvax.UUCP (Walter Maner) (06/15/89)

From article <613750053.2476@minster.york.ac.uk>, by alistair@minster.york.ac.uk:
> I would like to use animations of algorithms (searches, sorts, tree-building and traversal
> etc) in an undergraduate course. Does anyone know of any software available to
> do this - before I set out and re-invent the wheel?
> 
Maybe this will be of use to you:

----
From:         Karl-L. Noell <NOELL%DWIFH1.BITNET@wiscvm.wisc.edu>
Subject:      Sort Demo
Date:         Tue, 01 Sep 1987 15:30 CET

I'd like to contribute something for your info-ibmpc lending library.
It's a collection of Turbo-Pascal programs to illustrate various sorting
algorithms by real time animated pixel graphics.  Enclosed please
find  SORTDEMO.DOC and SHELL.PAS as *one* example.  The whole
package has about 800 recs.  Please let me know, if you are interested,
and tell me how to submit this stuff.

Regards
Karl-L. Noell
fhw (Wiesbaden, W.Germany)

   Graphic Illustration of Sorting Algorithms     K.L. Noell 01.Sep.87


It's difficult to explain sorting algorithms merely by verbose expla-
nations.  They are either easy to understand and simple to design but
they are very slow and inefficient;  or they run fairly quick but their
design and implementation is rather complex and troublesome.

For teaching purpose I realized an idea which illustrates various
sorting algorithms with the aid of real time animated pixel graphics.
Keys to be sorted are 640 random integers distributed over the inter-
val [0 ... 199].  These elements are stored in an array which is mapped
to corresponding pixels ( x:[0...639], y:[0...200] ).

In the beginning, this pixel distribution looks like a starry sky. After
the sorting procedure is started, you can watch its progress directly.
Swapping and moving of elements cause appropriate screen updates by
shifting the pixels towards their final ascending order.  Depending on
the particular sorting strategy, this works very slow and fussy or it is
intelligible sophisticated and quick.  You can compare features and
performance of different sorting algorithms;  after processing the
randomly distributed keys, the sorting can be started once more to deal
with an array already sorted, but in opposite (descending) order which
gives sometimes the worst case.  Swaps and loops (comparisons) are
counted.

Turbo-Pascal programs are provided to demonstrate the following sorting
algorithms:

BubbleSort,  HeapSort,  LinearSort,  QuickSort,  ShakeSort,  ShellSort .


My examples are based on sorting algorithms from the following books:

A.V. Aho; J.E. Hopcroft; J.D. Ullman:  Data Structures and Algorithms.
          Addison-Wesley, Amsterdam etc (1983)

Sara Baase: Computer Algorithms: Introduction to Design and Analysis.
          Addison-Wesley, Amsterdam etc (1978)


I have written and tested these programs with Turbo-Pascal (3.01A) under
DOS 3.1, running in an IBM-AT02 and also in clones with CGA and EGA.


                  ===>  Disclaimer Notice  <===

       This SORTDEMO.PAS - package is provided for educational
       purpose.  Neither the author nor the distributor makes
       any warranty or assumes any liability or responsibility
       for accuracy, completeness or usefulness.
       All risk of use is on the user.
       It may be freely copied but may not be sold for profit.
       Please keep the credits which refer to author and provenance.


Suggestions, problems:  please send E-mail to  NOELL@DWIFH1.BITNET

                        or contact:            Prof.Dr. Karl-L. Noell
                                               FHW - FB MND
                                               Am Brueckweg 26
                                               D-6090 Ruesselsheim
                                               (W. Germany)

[The program is in the library as SORTDEMO.PAS If there is a popular
demand we will bring over all the sort demos. -wab]


-- 
CSNet    maner@andy.bgsu.edu           | 419/372-8719
InterNet maner@andy.bgsu.edu 129.1.1.2 | BGSU Comp Sci Dept
UUCP     ... !osu-cis!bgsuvax!maner    | Bowling Green, OH 43403
BITNet   MANER@BGSUOPIE

duncan@dduck.ctt.bellcore.com (Scott Duncan) (06/15/89)

In article <4253@bgsuvax.UUCP> maner@bgsuvax.UUCP (Walter Maner) writes:
>
>I'd like to contribute something for your info-ibmpc lending library.
>It's a collection of Turbo-Pascal programs to illustrate various sorting
>algorithms by real time animated pixel graphics.

Though not software, there was a great SIGGRAPH submission a number of years
(from a Canadian university -- I now forget which one) which did this as well,
ending up with a final section of film that showed 9 screens running in para-
llel.  It was dramatic!  Everything raced along (or so it seemed) fora bit,
then some algorithms finished, then others.  Finally the credits came on, and
behind them, never finishing, was good old BubbleSort!  (The rest of the film
was excellent as well.  It won an award for its use of graphics to explain
sorting as each sort was illustrated earlier in the film and its algorithm ex-
plained -- no code, just the logic of the sorting method.)

Speaking only for myself, of course, I am...
Scott P. Duncan (duncan@ctt.bellcore.com OR ...!bellcore!ctt!duncan)
                (Bellcore, 444 Hoes Lane  RRC 1H-210, Piscataway, NJ  08854)
                (201-699-3910 (w)   201-463-3683 (h))

jae@ecsvax.UUCP (Jeff Ersoff) (06/15/89)

In article <16824@bellcore.bellcore.com>, duncan@dduck.ctt.bellcore.com (Scott Duncan) writes:
> 
> Though not software, there was a great SIGGRAPH submission a number of years
> (from a Canadian university -- I now forget which one) which did this as well,
> ending up with a final section of film that showed 9 screens running in para-
> llel.  It was dramatic!  Everything raced along (or so it seemed) fora bit,
> then some algorithms finished, then others.  Finally the credits came on, and
> behind them, never finishing, was good old BubbleSort!  (The rest of the film
> was excellent as well.  It won an award for its use of graphics to explain
> sorting as each sort was illustrated earlier in the film and its algorithm ex-
> plained -- no code, just the logic of the sorting method.)


This is indeed a fine film for giving the viewer an intuitive feel for 
various sorting algorithms. Its major weakness is the repetitive and 
almost comical pseudo-computer "music" in the background during sorts.
It is titled "Sorting Out Sorting". Two years ago it was available on 
videotape and 16mm film from
        Media Centre - Distribution Office
        University of Toronto
        121 St. George St.
        Toronto, Ontario
        CANADA M5S 1A1
 
				-jeff ersoff

michele@aucis.UUCP (Michele Pezet) (06/16/89)

In article <613750053.2476@minster.york.ac.uk>, alistair@minster.york.ac.uk writes:
> I would like to use animations of algorithms (searches, sorts, tree-building and traversal
> etc) in an undergraduate course. Does anyone know of any software available to
> do this - before I set out and re-invent the wheel?

As a part of my Senior Honors Research, I developed a set of programs
which animate several of the algorithms commonly taught in an
introductory data structures class.  
 
One program illustrates searching procedures (the serial search on 
unordered and ordered lists and a binary search), the second 
demonstrates various common sorts (insertion sort, selection sort, 
bubble sort, Shell's sort, quick sort, and heap sort), and the third 
presents various procedures on a linked list (insertion, deletion, and 
searching).  Each program includes a listing of each algorithm which 
it demonstrates.  I attempted to present each task as dynamically as 
possible to encourage students to visualize the processes involved.  
 
The programs were designed to be used both in the classroom for 
demonstration and out of the classroom for hands-on practice.  I wrote 
them in Turbo C 2.0 on an IBM PC compatible.  They do require a 
monitor capable of supporting at least CGA 80-column color text mode.
 
I have not yet distributed these programs in any way, but I would like 
to see them used.  Unfortunately, I am unsure on how to go about this 
task.
 
I wouldn't mind releasing them to the public domain if there is any 
interest, but I am unfamiliar with any legalities regarding public 
domain software.  I don't want to be held responsible for any problems 
that people think my programs have caused, and I don't want anyone to 
distribute them for commercial or profit-making uses.
 
If any of you can tell me what type of disclaimer I need to use, or 
where I can find information about any legal aspects or problems 
regarding the release of software to the public domain, I would really 
appreciate it.  I would also like to know if there is interest in 
these programs, and if so, what is the best way to distribute them.  
 
Thanks in advance!
 
Michele Pezet                                       ...!sharkey!aucis!michele
Andrews University                     michele%aucis.uucp@mailgw.cc.umich.edu
Computer Information Science Dept
Berrien Springs, MI 49104
 

pattis@june.cs.washington.edu (Richard Pattis) (06/16/89)

  Have there been any studies evaluating algorithm animations (not conducted
by people who have written such systems)?  I am unsure whether such aids are
ultimately a help or hinderance to students.  Given a fixed amount of time,
are there better alternatives (even if the students think watching animations
fun and informative)?

  For example, do students learn more from doing their own hand simulations?
I have seen students nod their heads (in understanding) while watching me
illustrate an algorithm (on an overhead); but often these same students have
little idea what they really saw, or how to duplicate my hand simulations.
How about getting the students to try and prove (I use this term loosely
here; read it as argue persuasively) that an algorithm is correct?  They can
either try to discover invariants or be supplied with them by the instructor.
Is spending time in either of these pursuits more productive than watching
animations?  Is the whole concept of "watching" too passive?  Are there
systems that require some active participation from the observer?

  It seems that somewhere along the line students must learn to think
abstractly (lest too many visualization details bog them down; when I draw
n-ary trees, I show the the students how they should be conceptualized,
independent of how they are implemented - first child/next sibling pointers,
when drawn out, are a mess). Is helping students visualize algorithms at this
stage in their education (college frosh/soph) going to hinder their ability
to think abstractly later?

  Certainly algorithm animations look neat (and are great programming
projects); but do they have an educational benefit?


Rich

PS: Marc H. Brown's, "Algorithm Animation" was published as an ACM
Distinguished Dissertation (1987) by the MIT press.  The system described
runs in Brown's (the university) Apollo lab. At some time they were supposedly
going to port everything to the Mac (in stage one, the Mac could display a
previously generated animation; in stage two, it could generate and display
its own animations). Sedgewick's book, "Algorithms" (2nd edition, published by
Addison-Wesley) uses still pictures from this system.

reggie@dinsdale.nm.paradyne.com (George W. Leach) (06/19/89)

   Some references on Algorithm Animation and Program Visualization.  This is
not up to date and is by no means complete.

%A Borning, Alan,
%T ThingLab - A Constraint-Oriented Simulation Laboratory
%R Technical Report SSL-79-3
%O Xerox Palo Alto Research Center
%C Palo Alto, CA
%D July, 1979


%A Myers, Brad,
%T Incense: A System for Displaying Data Structures
%J Computer Graphics
%V 17
%N 3
%D July, 1983
%P 115-125

%A Brown, Marc H.,
%A Sedgewick, Robert,
%T Techniques for Algorithm Animation
%J IEEE Software
%V 2
%N 1
%D January, 1985
%P 28-39

%A London, Ralph L.,
%A Duisberg, Robert A.,
%T Animating Programs Using Smalltalk
%J IEEE Computer
%V 18
%N 8
%D August, 1985
%P 61-71.

%A Wagner, Richard M.,
%T Program Animation Tools and Techniques
%R MS Thesis
%O Massachusetts Institute of Technology
%C Cambridge, MA
%D November, 1985

%A Myers, Brad,
%T Visual Programming, Programming by Example, and
%T Program Visualization: A Taxonomy
%J Proceedings of 
%K chi'86
%V 17
%N 3
%D July, 1983
%P 115-125

%A Duisberg, Robert A.,
%T Animated Graphical Interfaces using Temporal Constraints
%J Human Factors in Computing Systems, CHI'86 Conference Proceedings
%I ACM
%D April 1986
%P 131-136

%A Borning, Alan,
%T Defining Constraints Graphically
%J Human Factors in Computing Systems, CHI'86 Conference Proceedings
%I ACM
%D April 1986
%P 137-143

%A Solin, Ulla,
%T Animation Techniques for Parallel Algorithms
%R Report A50
%I Department of Computer Science, Abo Akademi
%C Turku, Finland
%D July 1986

%A Duisberg, Robert Adamy,
%T Constraint-Based Animation: Temporal Constraints in the Animus System
%R Ph.D. dissertation, Technical Report 86-09-01
%I Computer Science Department, University of Washington
%C Seattle, WA
%D August 1, 1986

%A Borning, Alan,
%A Duisberg, Robert,
%T Constraint-Based Tools for Building User Interfaces
%J ACM Transactions on Graphics
%V 5
%N 4
%D October 1986
%P 345-374

%A Bentley, Jon L.,
%A Kernighan, Brian W.,
%T A System for Algorithm Animation: Tutorial and User Manual
%R Computer Science Technical Report No. 132
%I AT&T Bell Laboratories
%C Murray Hill, NJ
%D January 1987

%A Hyrskykari, Aulikki,
%A Raiha, Kari-Juoko,
%T Aladdin: A Tool for Generating Algorithm Animations
%R Report A-1987-6
%I Department of Computer Science, University of Tempere
%C Tempere, Finland
%D April, 1987

%A Brown, Marc H.,
%T Exploring Algorithms Using Balsa-II
%J IEEE Computer, 21(5), May 1988, pp 14-36

%A Brown, Marc H.,
%B Algorithm Animation
%O 1987 ACM Distinguished Dissertation
%I ACM-MIT Press
%D June, 1988

%A Brown, Marc H.,
%T Perspectives On Algorithm Animation
%J Human Factors in Computing Systems, CHI'88 Conference Proceedings
%I ACM
%D May 1988
%P 33-38

%A Hughes, Charles E.
%A Moshell, J. Michael
%T Action Graphics: A Spreadsheet-Based Language for Animated Simulation
%I Computer Science Department, University of Central Florida
%C Orlando, FL
%D May 31, 1988

%A Mears, John E.
%A Hughes, Charles E.
%A Moshell, J. Michael
%T Designing Training Senarios by Rehearsal
%J 1988 Workshop on Visual Languages
%I IEEE
%D October 1988

George W. Leach					AT&T Paradyne 
.!uunet!pdn!reggie				Mail stop LG-133
reggie@pdn.paradyne.com				P.O. Box 2826
Phone: (813) 530-2376				Largo, FL  USA  34649-2826

twl@brunix (Theodore W. Leung) (06/19/89)

John Stasko, has just finished his PhD thesis on a system for
animating algorithms.  His system is called TANGO.  For more
information, you can mail to John as

jts@cs.brown.edu
John Stasko
Box 1910
Brown University
Providence RI 02912

Internet/CSnet: twl@cs.brown.edu 	| Ted Leung
BITNET: twl@BROWNCS.BITNET		| Box 1910, Brown University
UUCP: uunet!brunix!twl			| Providence, RI 02912