Problem Solving Techniques for the Design of Algorithms
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 algorithms data- flow representation. Finally, the details of the problem spaces provide a model for building a robust automated system.
- Statistics and Probability