Browse Prior Art Database

Problem Solving Techniques for the Design of Algorithms Disclosure Number: IPCOM000148141D
Original Publication Date: 1982-Nov-23
Included in the Prior Art Database: 2007-Mar-29
Document File: 36 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Kant, Elaine: AUTHOR [+3]


Elaine Kant and Allen Newell

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 36

CMU-C S-82-145

Problem Solving Techniques for the Design of Algorithms

Elaine Kant and Allen Newell

Department of Computer Science

 Carnegie-Mellon University
Pittsburgh, Pennsylvania 15213

23 November 1982

This paper will appear in Information Processing and Management.


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 arid modify the representations; these operators are adapted to the current problem state by means-ends analysis. The problem space also includes knowledge-rich schemas 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 process of discovery. We have observed that the time a subject takes 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.

This research is supported by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 3597, monitored by the Air Force Avionics Laboratory Under Contract F33615-81-K-1539. The views and conclusions contained in this document are those of the authors'and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the U.S. Government.

[This page contains 1 picture or other non-text object]

Page 2 of 36

[This page contains 1 picture or other non-text object]

Page 3 of 36

Table of Contents

1. Algorithm Design and Software Science 1 .l.

Automation methods for algorithm design
1.2. Why study how people design algorithms?
2. A Method for Studying Algorithm Design
2.1. The problem space theory
2.2. The role of protocol analysis
2.3. The issues
2.4. The problem domain
2.5. The subjects and the protocols
3. Case Studies
3.1. The problem
3.2. Overview of behavior of S2 on Algorithm GT (generate and test)
3.2.1. Summary of algorithm
3.2.2. The story of S2's solving attempt
3.3. Overview of behavior of S2 on Algorithm DC (divide and conquer)
3.4. Overview of behavior of 54 on Algorithm DC (divide and conquer)
4. A Model of Algo...