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