Teaching Reduction as an Algorithmic Problem-Solving Strategy

摘要

Reduction is a powerful strategy for solving proof and design problems in multiple contexts of computer science (CS). It is characterized by establishing connections between problems that may seem very different and by using black boxes. Therefore, reduction is closely related to CS abstraction. In particular, understanding and employing reduction requires one to differentiate between a problem and its solution. The latter is at a lower level of abstraction; it describes how the problem is solved, as opposed to the higher level of abstraction, which describes what the solution should achieve. A series of studies investigated the use of reduction indicating its limited use as well as specific difficulties in using it, in different contexts and age levels. In particular, the students tended to open black boxes when they used reduction and confused a problem and its solution. Following these outcomes, CS researchers presented some general guidelines for teaching reduction. The main ones recommended an explicit spiral teaching of reduction while emphasizing its characteristics and principles, and in particular, distinguishing between problems and solutions. We implemented these recommendations in an undergraduate course on algorithms and studied the effectiveness of our pedagogical framework. The findings indicate a substantial improvement in the students’ use of reduction.