Article:Reductive thinking in undergraduate CS courses
This paper discusses the role of reduction in computer science (CS) and describes a study on undergraduate computer science students’ perception of the concept of reduction. Reduction is an important problem-solving heuristic useful both for the theoretical aspects of CS, such as computability and algorithmics, as well as for many other CS facets, such as software design. Essentially, solving a problem by reduction means transforming it into a simpler problem (or problems) with a known solution, and constructing, or deducing, the solution to the original problem based on the solution(s) to the problem(s) to which the original problem was reduced. An important characteristic of reduction is using the solution to the reduced-to problem as a black box.
On a previous study [1] we learned that many high school students do not use reduction for solving computational model problems, and findings from another study [2] indicated some difficulties of undergraduate CS students in fully perceiving and acknowledging the notion of reduction in the context of computational models.
On this study we examined reductive thinking of undergraduate CS students, in a wider curricular context. We had three goals”>1. examine the tendency of undergraduate CS students, at different stages of their studies, to use reductive solutions when solving problems taken from a variety of CS areas. 2. Examine the issue of transfer in relation to reductive thinking, that is, whether students transfer their reductive thinking from the area of algorithmics, in which reduction is usually taught explicitly, to the field of computational models and the formal language theory, in which reduction is usually not taught explicitly despite the fact that it is an effective problem-solving heuristic in these areas. 3. Examine the ways undergraduate CS students conceive of and apply reduction.
The population consisted of 28 students, in three groups: 11 freshmen, at the end of their second semester, that had already studied CS1 and were about to complete CS2; 8 advanced students (at the end of their fourth or fifth semester), that had already studied or were about to complete a computational model course and an algorithm course; 9 prospective CS high school teachers. Interviews were conducted with students from group 1 and group 2. During the interviews group-1 students were asked to solve 4 CS1 algorithmic problems and group-2 students were asked to solve the same 4 questions, another 5 algorithmic problems on the algorithm course level, and 3 computational model problems. Group-3 students were asked to fill in a questionnaire, consisting of the 4 CS1 problems. The data was analyzed using qualitative methods.
Our findings demonstrated an evolving tendency to use reduction: First year students (who were exposed to reduction only implicitly) barely ever used reductive solutions, while the more mature students exhibited higher level of awareness to the concept of reduction, as well as to its potential use. However, difficulties in recognizing connections and identifying relations that allow for using reduction were found among freshmen as well as among advanced students. We saw a connection between the tendency to use reduction and the topics of the problems. Our findings also indicated that students did not transfer the tendency to use reduction from the area of algorithms to the area of computational models. For some students we noticed a notion of illegitimacy regarding the use of reduction.
Regarding the manner in which students applied reduction we noticed a few phenomena: Preferring relatively concrete solutions; Insistence on knowing the inside-details of the solution to the reduced-to problem; Reduction to a solution rather than to a problem; Not taking full advantage of the power of reduction when it is observed; Considering reductive solutions as inefficient (not tailored to the problem at hand); Underrating the difficulties of non-reductive strategies. Students had difficulties working with black boxes, and were trying to open the black box – before, during or instead of applying reduction.
Some of these findings can be explained by students not conceiving of reduction as a rewarding problem-solving heuristic that reflects high problem-solving skills. Other findings can be explained by a tendency to reduce levels of abstraction, reported in the contexts of mathematics and CS [3].
Based on these findings we recommend that in addition to the course material, habits of mind, such as reductive thinking, should be highlighted as well. Explicit discussion of reduction should start as early as possible, even during CS1. Reduction should be demonstrated in different situations and in various contexts and its role should be discussed explicitly.
This research was supported by the E. and J. Bishop Research Fund.
References
[1] Armoni, M., Gal-Ezer, J. and Tirosh, D. (2005). Solving problems reductively. Journal of Educational Computing Research, 32(2), pp. 113-129.
[2] Armoni. M. and Gal-Ezer, J. (2006). Reduction – an abstract thinking pattern”>The case of the computational models course. Proc. of the 37th SIGCSE Technical Symposium on Computer Science Education, pp. 389-393.
[3] Hazzan, O. (2003). How students attempt to reduce abstraction in the learning of mathematics and in the learning of computer science, Computer Science Education 13(2), pp. 95-122.
Author 1: Michal Armoni [email protected]
Author 2: Judith Gal-Ezer [email protected]
Author 3: Orit Hazzan [email protected]
Article Link: http://portal.acm.org/citation.cfm?id=1140161&coll=portal&dl=ACM&CFID=9122936&CFTOKEN=32438184