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…
Showing first 3,000 characters of 32,252 total.
Open the full document →
