Understanding and Automating Algorithm Design

1. Objects and operators

The basic objects for describing algorithms in the algorithrn design space are components that specify basic types of processing. These components may test whether a property holds, generate the elernents of a set one at a time, achieve an input / output relationship, apply a dornain operator. select a subpart of a cornpound object, or rnodify a rnemory of objects.

The algorithm cornponents are connected by links that allow flows of data and/or control and rnay be augrnented with assertions about their properlies or about their relationship to other objects or operators in any of the problern spaces. For example, a selection criterion rnight be to pick the bottorn left point frorn a set of points. New cornponents can be defined in terrns of old ones by adding additional standard inputs or outputs or by adding assertions, or a cornponent can be defined as configurat1on of other cornponents.

·See Section IV.E or [2] for a comparison with the search problern in program synthesis.

The assertions associated with cornponents rnay include inforrnation about the types of data objects expected as inputs or outputs or other preconditions or postconditions of processing, the ordering constraints on a generator, the criteria for selection. the initialization of a rnernory, expectations or conclusions about the time cornplexity of the algorithrn (cornponent) , constraints on the order of execution of the algorithrn cornponents, notes about the algorithrn (such as it has not yet been tested for the initial point ly1ng inside the hull).

Since algorithrns usually rnanipulate sorne sort of data, there are also representations of the cornrnon mathernatical concepts such as nurnbers or syrnbols and of sequences or sets of other objects. Assertions about tllese objects can be attached to descriptions of the object type or to items that represent specil1c data.

The number ol combinations of palfs from a set of elements is proportional toN squared (04.11

Divide and conquer a!gurithms can offen have run time of NlogN. (02.7, 01 .111

Tlle operators in the algorithrn description space are s1mple (syntactic) editing operations that add or modify cornponents. links between cornponents. and assertions. The knowledge is all located in the rules that suggest instantiations of the type of cornponents to create, the specific components to link, and the details of the assertions tobe added.

2. Operator selection

Selecting an operator (and instantiating it by selecting values for its argurnents) can be rnade rnore effective through the use of knowledge about general algorithrn design principles and about algorithrns in a particular dornain of application . This knowledge will be expressed here as rules. Otller such knowledge, such as how to handle specific problems raised during execution (the equivalent of a difference table for rneans-ends analysis) also Iimits the arnount of search necessary for operator selection.

The following set of rules about operator selection and instantiation is rnerely a representative sarnple of the knowledge that an algorithrn designer (human or otherwise) rnight have (not every designer has the sarne knowledge, of course) . Many other rules would add their suggestions and vetoes about what to do. II there is no consensus about what operator to apply, the fall back is search through the suggested possibilities.

lf a component needs to be refined and its outpul is a subsei of its input, refine the component to an element generate and test algorithm. (01 .1)

lf a component needs to be refined and its outpul is a structure that must satisfy certain constraints, refine it to an algorithm that builds a minimal structure and then adds units of structure until the constraints are satisfied. (01 .6] (An instance of this rule is suggested in [3].)

lf an afgorithm Iooks at part of the input many times to do the same kinds of tests, try saving information rather than recomputing, say with dynamic programming. [01 .1 O]

lf the characteristics of Subproblems produced by the divide step of a divide-and-conquer algorithm are unknown. then add the assertion that they are two equal-sized subproblems.

lf the characteristics of subproblems produced by the divide step of a divide -and-conquer algorithm are unknown, and if the set being divided is a set of points in two dimensions, then refine the divide step to be a sort of the points and a divis11J n tnto the points on eilher side of the median a line through the median . [02.3] This has a bit of dornain-specific knowledge although it is in the algorithm space.

II a component is missing a link to a required input, Iook for a component that has an Output with the same type (or havmg that type as a subpart or superpart) and connect the two cornponents.

3. Changing state

The state in the context ot a problern space changes primarily as a di rect result ot the successtul application ot an operator that modifies the algorithm description. II the operator application fails, and it there were competing Suggestions about what operator to apply, then alternative operators still apply and another will be tried . in addition to eilher tailing or succeeding, an operator may return a difficulty or opportunity. This becomes another goal to be worked on, perhaps in a different problern space. After processing of the new goal is complete (which may change the state in the algorithm description problern space) , the rules that caused the original operator to be selected may or may not be retriggered. II they are, the Operator application can be retried.

4. Changing problern spaces

One of the benefits of having multiple problern spaces is the ability to reduce search by working on the same goal in a different space. Same examples ot rules that can cause space changes are:

II a component needs to be re fined, and its outpul is a construct in space X, create exarnples of it and notice their properties. II this rule is applied, it will cause a transfer first to the example generation space and then to the domain space X. (01 .2]

II a configurat ion of components has not been shown to achieve the specifications of the cornponent of which it is a refinement, then syrnbolically execute it. (01 .9]

lf a configuration of cornponents has not been shown to achieve the specifications of the cornponent it is a refinernent of. and if symbolic execution has already been tried or is known in advance to be too cornplex to be informative, then execute the configuration an a concrete exarnple. (01 .2]

5. Goal satisfaction and c reatiol)

Recognition ot when goals have been achieved, or nearly achieved, of when to give up on a goal and declare tailure, of when to create new goals, and so on is crucial to enabling discoveries. Strict enforcement of hierarchical subgoaling would not allow the same tlexibility and creativity. Goal change knowledge can also serve as design heuristics. Some rules that express this knowledge are:

II an exponential algorithrn is created, try to irnprove it or find an alternative unless it can be shown that the problern is itself exponential. [02.6]

lf a/1 ob}ects added to a set have a cornrnon assertion. hypothesize that that property holds for a/1 elernents in the set and trv to substantiate the hypothesis.

II a component is defined by assertions that are appropriate for the Ievei of detatl currently desired (however that is deterrninedl}. then consider the cornponent acceptable.

lf a cornponent is not considered ro be reftned to an acceptable Ievei ul detail, then create a goal to re fine it.

G. The Application Domain Space

Algorithm designers need knowledge about their task domain as weil as about algorithm design in general. As an example of a problern space describing a task domain, consider the knowledge about geometry that can be used in solving the convex hull problems.

Obiects that are manipulatable in the geometric domain include points, lines, segments, angles, and polygons. Special properlies of object types or of specific objects may also be recorded. For example, the degenerate case of the object type polygen could be a point or line-segment, and a triangle would be the boundary case. For a specific geometric object, properlies would include being convex or being above or below a line.

The operators in the geometric domain include accomplishing such tunctions as drawing a line segment between two points and recognizing that a polygen is convex.

Any symbolic descriptions ot the objects in a figure and assertions about the objects or their relationships are available to the other spaces. For example, in the algorithm space, assertions may serve as test predicates, comparison or erdering relationships, or criteria tor extraction from compound object. Operators are available for execution, say to build a polygen in the example generation space or as an operator applied by a component in the algorithm space that can be run during test-case execution. but their internal workings are not available.

The domain space also includes recognition knowledge, expressed herein the form of rules. that if applied to a figure in the current focus of attention may cause recognition and/or the construction of a new object just as an operator application might. For example,

II two fine segrnents share a cornrnon endpoint, perceive the figure defined by that pair of segrnents as an angle. [02.6]

H. The Execution Space

The problern space in which execution occurs is an augmentation of the algorithm description space. lt uses the object type itern to represent the data processed by the algorithm that flow over the links between components. The items can represent either specific objects from the domain space (point A) or symbolic objects ("a point"). ltems can be augmented by properlies that are known to be true of them at a given point in the algorithm execution history- that a point is known tobe on or oft the hull or that it is the one most recently added to a memory.

The operators in this space control the sequencing of component execution and carry out component execution. lf asserlions needed to carry out the operators are missing, a difficulty is returned and a new goal to handle the difficulty is created.

Some instances of rules that suggest new goals to work on are:

lf the Input for test-case execution is uninstantiated, set up a goal to get an exarnple input. This will cause a transfer to the example generation space. A particular point set would be an example for the convex hull problem. (01 .3)

lf test-case execution shows that applying sorne Operation will rnake progress toward a solution of the problern but not solve it cornpletely, try rnodifying the description in the algorithrn design space to apply the Operation repeatedly (inside a loop) .

I. The Example GenerationSpace

The example generation space is also an augmentation ot another space, the domain space. Objects must be augmented by properlies that describe their typical instances, degenerate instances, boundary cases, and so on, it such information is not already present in the domain space. For instance. sequences consisting of repeated copies of the same elementare not typ1cal. Some sample operators are those that add and remove elements from examples. Seme sample rules are

lf creating an input to a generate-and-test algorithrn ana a/1 elernents in the input satisfy the test, then add another element (01.10]

II creating an example for test -case execution of an algorithm that has not yet been checked for correctness, pick non ­ degenerate objec t ~; and constructors.

IV. Design Automation Strategies

This section summarizes the model of human design and compares it to some of the other approaches suggested for fully or partially automating algorithm design and for automatic programming. lt also discusses how the methods might be extended to handle the problems in other contexts, such as interactive design.

A. Summary of Human Design

Several of our designers succeeded in creating convex hull algorithms. The algorithms and key discoveries of designers 01 and 02 have already been described. 01 's generate-and-test algorithm had a disappointing warst case run time proportional to the cube of the number of input points. But 01 would never have been able to design the anticipated linear algorithm. 1! can be shown that the problern of finding a convex hull is related to the problern of sorting, so under conventional assumptions 1t must be an NlogN problem. Eventually 01 went on to try a divide-and­ conquer approach that , with a little help from the experimenters. became a successful NlogN algorithm similar to 02's. Some other designers successfully recreated some convex hull algonthms that they had heard or read about but did not remember very clearly. (Many interesting convex hull algorithms have been described in the Iiterature [19) .) Stillother designers failed to find any algorithm at all. We also gave our designers some other problems. They were asked for algorithms to find the closed pair of points from a given set or the intersection points of a set of vertical and horizontal lines. Most designers quickly suggested brute force algorithms (which have a worst case run time !hat is the square of the size of the input) but were unable to find any of the Iaster algorithms.

The methods observed in human design are quite varied. Selecting and sticking with a kerne! idea provides a necessary focusing of attention, and using execution as an assertion propagation mechanism continues that focus and avoids the extensive search process that unlimited inference or search through the network of all refinements would entail. Of course if specific knowledge about the domain or algorithm design is available. it can be used to Iimit search by suggesting refinements directly. A powerful source of creativity is the use of visual reasoning about specific examples, which paves the way for discoveries about key concepts in algorithms. Although our current set of studies of human designers has provided many good ideas for a model of design, we would like to do more studies on other types of algorithms and on even more expert algorithm designers.

ln general , the designers' success was highly correlated with their interest in and background in algorithm design. Some problems that they had stemmed from an incomplete (or totally absent) understanding of design principles such as divide and conquer (which is very relevant to the examples we gave). Other problems seemed to be due to impatience with methodically following a design strategy. ln some cases, the designers tried to mix aspects of the design from two different approaches. This typically failed when they tried to mix subparts of different types of princ1ples but succeeded when they tried to reuse facts or theories from the geometric domain that were learned in an earlier design.

B. Automatie Programming

Automatie programming is that ever receding goal of automating the programming of everything the user wants with a minimal amount of specification. Automatie programming encompasses (1) algorithm design, (2) program synthesis, and (3) the problern of managing complexity in programming in the large. Algorithm design has been defined in Section I.A as the process of producing a computationally feasible program sketch (that is relatively complete and consistent) from a speci fication of what is to be accomplished. We refer here to the hour-level form of algorithm design, not research design. This routine design often precedes program synthesis. Program synthesis is the process of choosing data structures and access functions to transform a given algorithm specification into concrete code in a convent ional programming language. Like algonthm design. program synthesis requires intelligence, especiall y to produce extremely effic1ent code, but it probably can be achieved wi th more straighttorward techniques.

As has been pointed out by others [2. 10). full -fledged automatic programming requires the mcorporat ion of domain knowledge as weil as detailed coding knowledge. Furthermore. programming in the !arge must be supported by effect ive bookkeeping. There are Iew concrete results in this area, however. The notion of working in multiple spaces, and in a domain space in particular. may prove valuable in automating the entire programming process.

C. Formal Derivation

The formal derivation approach has been proposed for both algorithm design and program synthesis (25, 5, 21 ]. Formal derivation methods share with the design methods described here a refinement strategy based on a Iew, largely syntactic, transformations, but differ in !hat the Iransformations preserve correctness. lt is assumed that the specifications are correct and complete, and since the Iransformations require and guarantee correctness, then the intermediate states and the result are also correct and internally consistent. The operations of the Iransformations- defining new constructs, expanding definitions ("unfolding") , noticing instances of definitions that have arisen alter rearrangement and simplification of the algorithm constituents (" folding") - are similar to the processes that we have noted in human design.

One way !hat the formal approach differs from the model of design described here isthat it requires !hat terms be defined by axioms or equations and does not allow the use of terms defined only in a domain space. Also, in the formal approach, Iransformations are instantiated via axioms about the domain or algorithmic constructs; in the model of design described here, they can be instantiated by similar knowledge based on formal definitions. by arbitrary selection, or by guesses based on Observations of the domain. As discussed earlier, people can sometimes derive algorithms even if they do not have formal definitions of all the concepts. They need only have operators in the domain space that recognize the concepts, more primitive operators in the domain space that can construct the structures they want to recognize and techniques for implementing the constructive operators in the algorithm space. in contrast. the formal derivation approaches alten have problems wi th controlling the search process and wnh creating useful auxiliary definitions- the "aha" or "eureka" steps are often definitions inserted by human interaction. These problems result from there being no clues in the formal approach about how to introduce the right interesting knowledge.

Another way the formal approach, with its requirement for consistency and completeness, differs from human design is in the handfing of boundary conditions and base cases. The formal approach requires that these be defined early on, almost the opposite of the human approach. Getting the details of the boundary conditions right is one cause of the search problern in formal systems- there are many ways to clefine these conditions, and selecting the precise specifications or introducing conditionals and filling out the details adds complexity.

For some people, the discipline of taking care of details with a standard methodology releases their creativity. On the other hand, many people find it difficult to state invariants precisely if they must be absolutely correct. Getting the main idea of the invariant is crucial to solving the problem, but stating it formally to avoid such problems as fencepost errors makes it tedious and not obviously productive. For these people, getting the details right immediately is extremely difficult; the overhead of internalizing this methodology is prohibitively high.

Formal derivation systems are being augmented with more detailed knowledge about design techniques so that the search control can be more goal oriented [9] and also with knowledge about example generation [4). However, this still doesn't postpone settling all the details (having a domain space Iets you tinesse formalizing them) or say where the creative definitions come from (cross fertilization from domain spaces and other algorithms).

0 . lnductive lnference

lnductive inference from examples is another technique that has been explored, but more for the construction of small programs than for the design of algorithms or large systems. Unambiguously specifying the inputlautpul behavior of algorithms with examples is easier than so specifying the behavior of large programs. However, the inductive approaches usually rely on problern solving using a small set of schema, with little ability to improvise if none of the schema match. II the target language is logical equation based language with a search mechanism built into the interpreter, then this approach may werk [24) . But it is unlikely to produce clever algorithms in conventionallanguages.

E. Program Synthesis by Refinement

The program synthesis problern is complementary to that of algorithm design, although we would expect that many of the ::;ame problern solving techniques are used . The stage at which the algorithm design process stops -- when an algorithm is "understood" - should provide an appropriate specification or starting place for program synthesis.

The standard refinement paradigm in program synthesis [13, 23] is to apply knowledge-based rules and search over that knowledge; no creativity is introduced. The search problern is a bit different since once an algorithm is weil defined, the program synthesis problern is usually to find a more detailed program in a standard programming language selecting concrete data structures and accessing operations. Usually the search space is dense in correct solutions that vary in efficiency, reliability, modifiability, and so on [2]. Past research has investigated the control of the search by efficiency (for example, [14]) . Such control is not a definitive solution, but many approaches have been prototyped fairly successfully.

As in most expert systems, it is assumed !hat all the knowledge about how to refine programming constructs is present in the refinement rules. ln contrast, the hypothesize and test technique in the design modal presented here allows the discovery of new programming techniques. The price paid, of course, is that more search at the lower Ieveis is required, and this search is not as easily controlled by efficiency rules.

F. Program Synthesis by Design

We hope that algorithm design research will .result in aids for program synthesis that avoid hand coding of all the refinement rules. The initial knowledge base requirements should be simplified considerably as a result of the more generic problem· solving abilities such as trial execution, with its low-level means ends analysis and search, and domain space reasoning. Putting in more of this creativity should make the automatic programming process more flexible and robust and may even produce better programs.

G. lnteractive Tools

An interesting question to ask is. does this knowledge suggest any other tools to aid in the design process? Are there some interactive tools that might help people in the design process? Or is there some novel mix of human and machine power that could Iead to even better design?

The conventional wisdom is that people have better insight and machines are better at the details. Following this wisdom. the machine could suggest the full range of possible approaches at any one step and the person could decide which to follow. providing the search control.

We could augment this plan by observing that execution is a powerful technique in design. Programsare good at methodically following algorithms for execution, but people frequently see what they expect and miss some of the problems. This would suggest machine support for execution of designs. The execution would expose problems and inconsistencies that people might skip over and the people could suggest some solutions to the problern or suggest new directions to follow.

in addition, the machine support could include a set of rules that continuously monitor simple features of the design, providing a check !hat preserves almost-correctness but does not guarantee a complete validation. in effect, this makes the machine a sounding board for human design, just as colleagues act as sounding boards. People explain their ideas to colleagues so that they are forced to Iook at their design from other perspectives (with different assumptions) and go through the design one more time in explaining it. A machine might serve the role of a colleague.

Building the human/machine communication interface is the hard part of following through with these plans. The two agents must speak the same language and each must be able to track what the other is doing. This may turn out to be even harder than full automation.

H. Other Design Tasks

There are a variety of other design tasks, such as engineering design or VLSI design. Although each of these tasks has its own uniqua characteristics, we may hope that some of the concepts discussed in this paper may be relevant to these tasks.

V. Conclusions

The Jssence of the modal of design presented here lies in its informality and its use of multiple problern spaces. including example generation and trial execution based on both the domain space and an algorithm design space. These techniques provide a focus of attention to Iimit search and enable the discovery of key concepts. The model shares problem-solving techniques with many of the other approaches, but rather than having a s1ngle monolithic plan of attack, it shifts techniques depending on the knowledge available.

Several areas need further formalizing and testing The rnodels of the processes of discovery and visual reasoning must be ex tended. Learning and database issues slwuld be explored further. For example. what are the appropriate organizat10n and retrieval techniques for large amounts of information so that key ideas in algorithms and derivattons are accessible when relevant? Being able to !earn automatically depends on appropriate accessing and on general problern solving techniques.

The interactions between search . domain knowledge, and programming knowledge seem important in tasks of any appreciable difficulty, including automatic programming and the next generation of expert systerns, but several questions about these interactions are stil l unresolved. For example, it is not weil understood how to determine when to stop refining at a given Ievei. how problern spaces are created frorn problems descriptions, and so on .

Understanding the design process impacts other branches of Al. Those that include design tasks, discovery, visual reasoning, the use of examples, and interaction between different types of knowledge could be compared to algorithm design in their organization of knowledge and use of problern-solving techniques. Answering the questions posed for design should shed some light on the general issues in other domains. A side effect of automation, the formalization of algorithm design, analysis, and optimization principles, could also be useful in teaching. Our Observations of human design show that examples are useful in the absence of knowledge and therefore probably necessary to teach the knowledge, but having explicit principles is more efficient for the designer.

ln summary, the model of design presented here is a good start on understanding algorithm design. The attempt to formalize the modellays a substantial part of the foundation for automation.

Acknowledgments

The research described here is joint work with Allen Newell and David Steier. Mary-Anne Wolf recorded and transcribed many of the protocols. Thanks to Jon Bentley for helping to instigate these studies. Thanks arealso due to the designers who participated in the experiments for their interest and cooperation; they shall remain anonymaus for obvious reasons. Programming support for the implementation and additional input has been provided by Brigham Bell , Lisa Covi . Billy Kim. Roland Kovacs. Deepak Kulkarny, David MarshalL Jim Muller. Ed Pervin. Eric Schwabe. Mark Taylor, and Ross Thompson as weil as Wolf and Steier. Allen Newell , David Barstow. David Steier. and Sol Greenspan made valuable comments on earlier versions of this paper.