Balsa Manual

MacBALSA Version Aleph Marc H. Brown Copyright c 1989 by Marc H. Brown. All rights reserved. This manuscript and the accompanying software are prelimi- nary, experimental, and under active development. They are also copyrighted. Do not copy either or distribute either without prior written permission. Preface This manuscript and the accompanying MacBALSA software are predicated on the thesis that computer algorithms are best understood through interactive simulations: that “a picture is worth a thousand words;” that a moving picture is worth much more; and that the ability to interact with a movie is invaluable. The intent is to exploit the capabilities of the computer as a communications medium, bringing to life concepts presented in conventional textbooks, and transforming you, the reader, from a passive observer into an active participant in the study of a variety of fundamental and important algorithms and data structures. The manuscript contains documentation for using the software, and the software contains the MacBALSA runtime environment with interactive simulations from a variety of fundamental algorithms in the realms of sorting, computational geometry, graphs, and binpacking. Both are preliminary and not ready for wide-spread distribution; they are available by contacting me directly. What I hope will be ready in the near future for general distribution is an “exploratorium for algorithms:” a book containing exercises that utilize animated algorithms within the MacBALSA environment. The exploratorium will not replace a standard textbook, but rather will complement one. The software will contain interactive simulations of textbook algorithms (as in the software accompanying this manuscript), and the exploratorium book will contain exercises that make use of the software. The software could be used by an instructor during a lecture (in a lecture hall with Macintoshes or appropriate projection equipment), showing computer “videotapes” in lieu of static diagrams on blackboards or viewgraphs; by students for homework or during a laboratory session; or by an individual on his own. 3 4 Preface The algorithms I intend to cover are from the domains of sorting, searching, computational geometry, graphs, and fundamentals. The complete list is as follows: Sorting: selection sort, insertion sort, bubble sort, shaker sort, Shellsort, quicksort, radix sorting, and heapsort. Searching: array methods, binary search trees, balanced trees, and hashing. Computational Geometry: closed paths, point inclusion, convex hulls, range searching, line intersection. Graphs: depth-first and breadth-first traversals, union-find, minimal spanning t…