Problem Solving Techniques for the Design of Algorithms
Abstract
By studying the problem-solving techniques that people use to design algorithms we can learn something about building systems that automatically derive algorithms or assist human designers. In this paper we present a model of algorithm design based on our analysis of the protocols of two subjects designing three convex hull algorithms. The subjects work mainly in a data-flow problem space in which the objects are representations of partially specified algorithms. A small number of general-purpose operators construct and modify the representations; these operators are adapted to the current problem state by means-ends analysis. The problem space also includes knowledge-rich schemes such as divide and conquer that subjects incorporate into their algorithms. A particularly versatile problem-solving method in this problem space is symbolic execution, which can be used to refine, verify, or explain components of an algorithm. The subjects also work in a task-domain space about geometry. The interplay between problem solving in the two spaces makes possible the processes of discovery. We have observed that the time a subject tasks to design an algorithm is proportional to the number of components in the algorithm's data- flow representation. Finally, the details of the problem spaces provide a model for building a robust automated system.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 23, 1982
- Accession Number
- ADA125211
Entities
People
- Allen Newell
- Elaine Kant
Organizations
- Carnegie Mellon University