DSMITH@RUTGERS.ARPA (04/09/84)
[Forwarded from the Rutgers bboard by Laws@SRI-AI.]
Rutgers' Computer Science Colloquium
Semiautomated Algorithm Design
Douglas R. Smith
Algorithm design is viewed as the transformation of a formal specification
of a problem into an algorithm. We present a formal top-down method for
creating hierarchically structured algorithms. The method works as follows: to
design an algorithm A0 for a problem specification P0, the programmer
conjectures the overall structure S of A0, then uses knowledge of the
structure S to deduce subproblem specifications P1,...,Pn for the
underdetermined parts of S. Algorithms A1,...,An are then designed for the
subproblems P1,...,Pn and assembled (via the structure S) into an
algorithm for the initial problem P0. This process results in the
decomposition of the initial problem specification into a hierarchy of
subproblem specifications and the composition of a corresponding
hierarchically structured algorithm. The knowledge used to deduce
specifications for subproblems is obtained by analysis of the particular
structure S and is encoded in a procedure called a design strategy for S.
The top-down design process depends on design strategies for many
different kinds of algorithm structures.
We illustrate this approach by presenting the knowledge needed to
synthesize a class of divide and conquer algorithms and by deriving a
quicksort algorithm. Our examples are drawn from experiments with an
implemented algorithm design system called CYPRESS. Current efforts to
systematically acquire design strategies for fundamental classes of
algorithms will be discussed.
DATE: Thursday, April 12, 1984
TIME: 10:30 a.m.
PLACE: Hill Center - Room 705
* Coffee will be served at 10:00 a.m.