## (Experimental Problems in Psychology of Programming)

Psychology of programming research has regularly reused some problems as a basis for experiments. There is no canonical list of these problems as yet, so I am trying to build a list of the problems I find as I read the PoP literature. I have included a full bibliography, so it is possible to access a half-remembered problem by author. There are also some as-yet unpublished contributions in which people have described their own experimental tasks.

This list was last updated on 25 November 1996, and is no longer maintained.

The list is currently subdivided only by whether the problem has mainly been used in experiments that test comprehension, or whether it has been used to test implementation.

The "Noah" Problem
The problem is described by Rist (1995) as "Write a program that shows the average and maximum rainfall for a period. The end of the period is signalled by an input value of -99"
[implementation language: Pascal]
The Noah problem has been used by numerous other researchers for other languages. See Cunniff et. al. (1986)
[implementation languages: Pascal and FPL (a graphical language)]
and Soloway - I have not tracked down his original formulation.

The "Index" Problem
The problem is described by Booth (1992) as "Write a function index which takes a list (of type a list) and an element (of type a) and returns the position of this element in the list (the first element has the position 1 in the list). If the element does not appear in the list, an error message should be given"
[implementation language: Standard ML]

Three Prolog Problems
Noble (1992) set three problems in Prolog: to square all numbers in a list unless the value is less than 6, to add an element to the end of a list, and to delete the Nth element of a list.
[implementation language: Prolog]

The Discount Store Problem
Chen and Vecchio (1992) tested use of nested conditionals with a problem in which a price had to be calculated, dependent on the quantity of items purchased
[implementation language: BASIC]

Array Reversal Problem
Used by Green et. al. (1987) in a comparative language study. The problem is described as "reverse an array in place" or "reverse a list".
[implementation languages: Basic, Pascal and Prolog]

The Train Timetable Problem
A second problem in the Green et. al. (1987) study. The problem is described as "consult a timetable of Cambridge-London trains and find the last train to arrive at or before a stated time".
[implementation languages: Basic, Pascal and Prolog]

The "Traffic Counting" Problem
Derived from a standard Pascal text (Findlay & Watt 1978) by Ratcliff & Siddiqui (1985) and also used by Green et. al. (1987). The problem specification is "A traffic survey is conducted automatically by placing a detector at the road side, connected by data-links to a computer. Whenever a vehicle passes the detector, it transmits a signal consisting of the number 1. A clock in the detector is started at the beginning of the survey, and at one second intervals thereafter it transmits a signal consisting of the number 2. At the end of the survey, the detector transmits a 0. Each signal is received by the computer as a single number (i.e. it is impossible for two signals to arrive at the same time). Design a program which reads such a set of signals and outputs the following: a) the length of the survey period b) the number of vehicles recorded, c) the length of the longest waiting period without a vehicle."
[implementation languages: Basic, Pascal and Prolog]

The "Swim Meet Competition" Problem
This was derived from a problem in an object-oriented design textbook (Rumbaugh et.al. 1991) by Lee and Pennington (1994). The complete problem description rather long - it is given in an appendix to the paper. The basic requirement is to add up the scores achieved by different competitors across multiple swimming events, on an individual and team basis.
[implementation language: design only]

The "RJE" Problem
This problem, described by Scholtz & Wiedenbeck (1992), is described as follows: "You are asked to simulate a (simplified) version of a remote job entry facility which modifies and transmits data between two computers. Your program will do three things to each line of text read in: 1) Reverse the order of the characters. 2) Translate the upper case characters to lower case and vice versa. 3) If a line is less than 60 characters long, fill it with *'s and write out a line of length 60. If a line is greater than 60, write it out as separate lines of exactly 60, filling the last line with *'s if necessary."
[implementation language: Pascal and Icon (a string processing language)]

The Manufacturing Capacity Problem
Chatel et. al. (1992) used this problem to test transfer between familiar and unfamiliar languages: 'You have been contacted in order to set up a car factory management computing program. Various car models are to be manufactured. As the end of the year is close, one of the executives in charge of the production has asked you to estimate the car manufacturing capacity for the next year, i.e. the number of cars which may be manufactured with the available component parts in stock. This should make it possible, in the future, to order component parts according to the number of cars which are bought. In the first place, your program should answer the following question: "How many standard model cars can be manufactured with the component parts which are available in stock?" You will take into account only the external parts of the car and not the internal parts such as the engine, the seats etc.'
[implementation languages: Smalltalk, Pascal, C and Lisp]

A Matrix Append Problem
Pandey and Burnett (1993) used this to compare their Forms/3 environment to Pascal and APL. It is described as "Write a program in Pascal that appends two appropriately shaped matrices into a single matrix. For example the program applied to the matrices [two 3x3 matrices] returns the matrix [a 3 row by 6 column matrix]".
[implementation languages: Pascal, APL and Forms/3]

Fibonacci Sequence Problem
Pandey and Burnett (1993) used this at the same time as the matrix append problem. The problem is: "Write a program in OSU-APL that computes the first N elements of the Fibonacci sequence. In the Fibonacci sequence, the first two elements are 1, and each element after that is the sum of the previous two elements. For example, given an N of 10, the program produces: 1 1 2 3 5 8 13 21 34 55".
[implementation languages: Pascal, APL and Forms/3]

Updating Stock Problem
Hoc (1983) used this task to investigate the effects on programmer strategies of successive constraints introduced within a simulated computer. The problem is described as: "The subject's task is to perform transactions as indicated by the transaction file: e.g. '3 13' means 'add 13 to the quantity of item 3 in the old stock file' ... by the nature of the 'computer', files can only be traversed sequentially, and so all the transactions for a given item number must be done together. When all transactions for a given item are completed, the value of the old stock cell is sent to the new stock file."
[implementation languages: simulated computer]

Hoc (1981) compared two structured design methods by asking subjects trained in each method to spend 3 hours designing a program for allocating gift tokens to mail-order customers under a rather complicated set of rules. The paper describes these rules quite fully.
[implementation languages: flowcharts, then an unspecified language]

Drug Company Deliveries
Saariluoma & Sajaniemi (1994) compared spreadsheet programs in the case where the elements naturally formed rectangular areas, and where they didn't. Subjects had to write spreadsheet formulae to work out subtotals from a table of different categories of drugs against the number of deliveries in each month of the year.

Carpets and Wallpaper
Green and Navarro (1995) also investigated problems based on rectangular areas - but in the real world, rather than in a table of numbers. The program "took as data the dimensions of a set of rooms, plus constants for price and size of carpet rolls and of wallpaper rolls, and computed the total cost of carpets and of wallpaper (no allowance being made for doors windows etc.). Three different qualities of carpet were allowed for". (The complete program wasn't published but is available by ftp from Green's web page)
[implementation languages: LabView, Basic, Excel spreadsheet]

The Lift Control Problem
This is reported by Sonnentag (1996) and originally attributed to Guindon (1990). It is described as "design a software system that controls the movement of N lifts between M floors by taking into account various realistic constraints".
[implementation languages: Design only]

BASIC Comprehension Problems
Chee (1993) used the following problems to assess understanding of models of BASIC: translate algebraic expressions into BASIC; assess validity of assignment and increment statements; predict output of loop summing numbers from 1 to 4; calculate salary from hourly wage.
[implementation language: BASIC]

Lambda Expression Comprehension
Eisenberg et. al. (1987) tested understanding of Scheme, and particularly of lambda-expressions, with a series of expressions that carried out simple arithmetic operations in the context of function applications. The complete test set is included in an appendix to the paper.
[implementation language: Scheme]

The Family Tree Problem
This problem was used by Ormerod et. al. (1986) to test comprehension of one of the classic problem domains for introductory Prolog examples: relationships in a family tree. Two families were presented in diagrammatic form, or as listings of facts and rules. Subjects were asked to answer questions about the relationships between specific individuals, based on either the listing or diagrammatic representation. An alternative problem tested a less familiar domain by presenting a hierarchy of management functions that was homomorphic to one of the family trees.
[implementation language: Prolog]

The Shellsort Problem
Wiedenbeck (1986) Used an implementation of a shell sort algorithm in Pascal to test the effect of "beacon" lines on program comprehension and memory. The paper includes a listing of the Pascal procedure which was used as test material.
[implementation language: Pascal]

The "Rocket" Problem
Used by Curtis et.al. (1989), and attributed originally to Barrodale et. al. (1971), although they also cite its use by Shephard et. al. (1979) and Gilmore and Smith (1984). More recently, this problem was used in comprehension studies by Green et al. (1991), then by Moher et. al. (1993). Green et. al. describe the problems as: "The rocket program computes the path of a rocket of given mass; the structure includes a while-loop (until rocket lands), inside which is a conditional (the rocket tilts at time 11) and some arithmetic". Most of the uses of this problem have been comparing comprehension of graphical and text versions of the program. Curtis et.al. (1989) intended it to exhibit complex algorithmic requirements without complex data structures
[implementation languages: FORTRAN, flowcharts, generic text, LabView, Petri nets]

The "Airport" Problem
This has the same provenance as the Rocket problem, and was used for similar purposes. It is described by Green et. al. (1991) as a "simple Monte Carlo simulation, consisting of a for-loop (number of trials) containing two conditionals (random arrival or departure) and a nested conditional in which queues are serviced". Curtis et.al. (1989) contrasted it with the Rocket and Inventory problems as containing both complex algorithms and complex data structures.
[implementation languages: FORTRAN, flowcharts, generic text, LabView, Petri nets]

The "Inventory" Problem
This was also derived by Curtis et.al. (1989) from Barrodale et. al. (1971), but it was not picked up by Green et al. (1991). According to Curtis et. al., it "maintained an inventory for a grocery distribution center. It processed orders for items at multiple stores by fetching item records from a data base, decerementing the on-hand inventory by the size of the order, reordering stock if necesary, and preparing a bill for the total order." It was intended to express a simple algorithm operating with a complex data structure.
[implementation languages: FORTRAN, flowcharts]

The "Average" Program
This is one of a set of four programs used by Soloway and Ehrlich (1984) and also by Détienne and Soloway (1990). It "calculates the average of some numbers that are read in; the stopping condition is the reading of the sentinel value, 99999." These studies focussed on plan comprehension: a listing of the program is given in the Détienne and Soloway paper.
[implementation language: Pascal]

The "MaxNumber" Program
This is another of the set of four programs used by Soloway and Ehrlich (1984) and Détienne and Soloway (1990). It "finds the maximum of some numbers." A listing of the program is given in the Détienne and Soloway paper.
[implementation language: Pascal]

The "Maxsentence" Program
This is another of the set of four programs used by Soloway and Ehrlich (1984) and Détienne and Soloway (1990). It "tests to see if some variable contains a number that is greater than a maximum, and if so, the variable is reset to the maximum." (This is a prison sentence, not a text sentence; it is determined by a number of convictions). A listing of the program is given in the Détienne and Soloway paper.
[implementation language: Pascal]

The "SQRT" Program
This is another of the set of four programs used by Soloway and Ehrlich (1984) and Détienne and Soloway (1990). It caclulates the square root of 10 numbers. A guard prevents the square root being taken of a negative number. A listing of the program is given in the Détienne and Soloway paper.
[implementation language: Pascal]

The Backtracking Exercise
This was used by Taylor (1990) to study understanding of the backtracking mechanism in Prolog. It was first devised by Coombs & Stell (1985) in a study of backtracking errors. It consists of 10 clauses, listed in Taylor (1990) for which students were simply asked to describe the execution process.
[implementation language: Prolog]

Clients and Product Orders
This was used by Pennington (1987) amongst other programs that are not described to assess the representations built by COBOL and FORTRAN programmers while reading program text. The problem is also used by Curtis et. al. (1984) and Soloway et. al. (1983). Only the COBOL text is given in the paper. "This program solves a toy problem in which a list of clients and their product orders for a month are processed and average order sizes for two subsets of clients are computed".
[implementation language: COBOL and FORTRAN]

Petrol Pump Controller
This is described by Brooke and Duncan (1980) as being used to compare reading of flowcharts to (assembler-level) pseudocode. The paper includes a block diagram of the machine, a complete flowchart, and a complete pseudocode listing.
[implementation language: flowchart and pseudocode]

The Hungry Hare
This was originally described by Sime et. al. (1973) as a program to control the eating habits of a mechanical hare. Two synthetic languages were used, in which conditionals such as: (if (juicy) then (if (leafy) then (if (green) then grill) else boil) else fry) were expressed in either nested or GOTO form. The problem has since been adapted by Scanlan (1989) (amongst others) to compare flowcharts and pseudocode. A drawing of the mechanical hare itself can be found in Arblaster et. al. (1978)
[implementation language: synthetic languages, flowchart and pseudocode]

## References:

Arblaster, A.T., Sime, M.E. & Green. T.R.G. "Jumping to some purpose" The Computer Journal, 22(2), 105-109.

Barrodale, I., Roberts, F.D.K. & Ehle, B.L. (1971) "Elementary Computer Applications in Science, Engineering and Business" Wiley, New York.

Booth, S. (1992) "The experience of learning to program. Example: recursion." in Proceedings of The 5th Workshop of the Psychology of Programming Interest Group: INRIA, Paris

Brooke, J.B. & Duncan, K.D. (1980) "An experimental study of flowcharts as an aid to identification of procedural faults". Ergonomics, 23(4) 387-399.

Chatel, S., Détienne, F. & Borne, I. (1992) "Transfer among programming languages: an assessment of various indicators" in Proceedings of The 5th Workshop of the Psychology of Programming Interest Group: INRIA, Paris

Chee, Y.S. (1993) "Applying Gentner's theory of analogy to the teaching of computer programming" IJMMS 38, 347-368

Chen, H.-G & Vecchio, R.P. (1992) "Nested IF-THEN-ELSE constructs in end-user computing: personality and aptitude as predictors of programming ability" IJMMS 36(6), 843-860

Coombs, M.J. & Stell, J.G. (1985) "A model for debugging Prolog by symbolic execution: the separation of specification and procedure." Research Report No. MMIGR 137, Dept. of Computer Science, University of Strathclyde

Cunniff, N., Taylor, R.P. & Black, J.B. (1986) "Does programming language affect the type of conceptual bugs in beginners' programs? A comparison of FPL and Pascal". Proc. CHI '86.

Curtis, B., Forman, I., Brooks, R.E., Soloway, E. & Ehrlich, K. (1984) "Psychological perspectives for software science" Information Processing and Management, 20, 81-96

Curtis, B., Shephard, S., Kruesi-Bailey, E. Bailey, J.. & Boehm-Davis, D (1989) "Experimental evaluation of software documentation formats" J. Systems & Softwarew 9(2) 167-207

Détienne, F. and Soloway, E. (1990) "An empirically-derived control structure for the process of program understanding" IJMMS 33, 323-342

Eisenberg, M, Resnick, M & Turbak, F. (1987) "Understanding procedures as objects" in Empirical Studies of Programmers: 2nd Workshop: Ablex

Findlay, W. & Watt, D.A. (1978) "Pascal: an introduction to methodical programming" (1st ed.) pp60-66: Pitman

Gilmore, D.J. & Smith, H.T. (1984) "An investigation of the utility of flowcharts during computer program debugging" IJMMS 20, 357-372

Green, T.R.G., Bellamy, R.K.E. & Parker, J.M. (1987) "Parsing and gnisrap: a model of device use" in Empirical Studies of Programmers: 2nd Workshop: Ablex

Green, T.R.G., Petre, M. & Bellamy, R.K.E. (1991) "Comprehensibility of visual and textual programs: a test of superlativism against the 'Match-Mismatch' conjecture" in Empirical Studies of Programmers: 4th Workshop: Ablex

Green, T. R. G. and Navarro, R. (1995) Programming plans, imagery, and visual programming. In Nordby, K., Helmersen, P. H., Gilmore, D. J, and Arnesen, S. (1995) INTERACT-95. London: Chapman and Hall (pp. 139-144).

Guindon, R. (1990) "Designing the design process: exploiting opportunistic thoughts" Human-Computer Interaction, 5, 305-344

Hoc, J.-M. (1981) "Planning and direction of problem solving in structured programming: an empirical comparison between two methods" Int. J. Man-Machine Studies 15, 363-383.

Hoc, J.-M. (1983) "Analysis of beginners' problem-solving strategies in programming". In T.R.G. Green, S.J.Payne and G.C. van der Veer (Eds.) The Psychology of Computer Use. Academic Press.

Lee, A. & Pennington, N (1994) "The effects of paradigm on cognitive activities in design" IJHCS 40(4) 577-601

Moher, T.G., Mak, D.C., Blumenthal, B & Leventhal, L.M. (1993) "Comparing the comprehensibility of textual and graphical programs: the case of Petri nets" in Empirical Studies of Programmers: 5th Workshop: Ablex

Noble, R. (1992) "Preferential use of examples by novices learning prolog" in Proceedings of The 5th Workshop of the Psychology of Programming Interest Group: INRIA, Paris

Ormerod, T.C., Manktelow, K.I., Robson, E.H. & Steward, A.P. (1986) "Content and representation effects with reasoning tasks in PROLOG form" Behaviour and Information Technology 5(2) 157-168

Pandey, R.K. & Burnett, M.M. (1993) "Is it easier to write matrix manipulation programs visually or textually? An empirical study" In 1993 IEEE Symposium on Visual Languages.

Pennington, N. (1987) "Stimulus structures and mental representations in expert comprehension of computer programs" Cognitive Psychology 19, 295-341.

Ratcliff, B. & Siddiqui, J.I.A. (1985) "An empirical investigation into problem decomposition strategies used in program design" IJMMS 22, 77-90

Rist, R.S. (1995) "Program structure and design" to appear in Cognitive Science

Rumbaugh, J., Blaha, M., Premerlani, W., Eddy, F. & Lorensen, W. (1991) "Object-Oriented Modeling and Design", p.193: Prentice Hall

Saariluoma, P. & Sajaniemi, J. (1994) "Transforming verbal descriptions into mathematical formulas in spreadsheet calculation". International Journal of Human Computer Studies, 41(6), 915-948. Rumbaugh, J., Blaha, M., Premerlani, W., Eddy, F. & Lorensen, W. (1991) "Object-Oriented Modeling and Design", p.193: Prentice Hall

Scanlan, D.A. (1989) "Structured flowcharts outperform pseudocode: an experimental comparison". IEEE Software, September 1989.

Scholtz, J. & Wiedenbeck, S. (1992) "The role of planning in learning a new programming language" IJMMS 37(2), 191-214

Sheppard, S.B., Curtis, B., Milliman, P. & Love, T. (1979) "Modern coding pratices and programmer performance" Computer 12(12) 41-49

Sime, M.E., Green, T.R.G. & Guest, D.J. (1973) "Psychological evaluation of two conditional constructiuons used in computer languages". IJMMS 5, 105-113.

Soloway, E., Ehrlich, K. & Black, J.B. (1983) "Beyond numbers: Don't ask 'how many' ... ask 'why'" Proc. Conf. Human Factors in Computer Systems.

Soloway, E. and Ehrlich, K. (1984) "Empirical studies of programming knowledge" IEEE Transactions on Software Engineering, 10(5), 595-609

Sonnentag, S. (1996) "Planning and knowledge about strategies: their relationship to work characteristics in software design" Behaviour and Information Technology 15(4), 213-225.

Taylor, J. (1990) "Analysing novices analysing Prolog: What stories do novices tell themselves about Prolog?" Instructional Science 19(4/5), 283-309

Wiedenbeck, S. (1986) "Beacons in computer program comprehension" IJMMS 25, 697-709