Article: Is it really an algorithm – the need for explicit discourse
The notion of an algorithm is fundamental in computer science. Yet, it is not always fully conceived by novices. The paper focuses on a particular facet of algorithm conception – the relationship between an algorithmic problem, its analysis, and its desired algorithmic solution. The paper displays evidence that novices demonstrate cognitive obstacles regarding the notion of an algorithm, which relate to a process-object duality phenomenon and inadequate classroom norms of communication.
The paper presents a study, which involved 97 CS2 pre-college students who were asked to offer an algorithmic solution to the following algorithmic problem”>N players compete in a pairs-game competition; in each game there is a winner and a loser; the winner continues to compete and the loser immediately drops out; the competition ends when only one player remains. Develop an algorithm for which the input is N, the number of players, and the output is the number of games played.
The algorithmic task does not specify the way the games are structured. One may wonder whether it matters. Apparently it does not; that is, the output will be the same value for all possible structures. Yet, in order to see the latter, one should analyze the task at hand. Unfortunately, only a small minority of the students performed proper analysis (and realized that the output is N-1). Most students adopted a specific games structure (e.g., a binary tree); and solved the task for some values of N (e.g., a power of 2), by emulating the competition process in their selected structure.
The results reveal cognitive obstacles in students’ understanding of the notion of an algorithm. Students demonstrated several limited conceptions: 1. Algorithms embody processes; they are not I/O objects; 2. (too) Short algorithms (e.g., no-loop) are unacceptable; and 3. An algorithm “serves as a proof of its own correctness”; thus, following its execution on a particular input example suffices. Following the results, several didactical recommendations are offered to CS tutors, in order to address the revealed cognitive obstacles.
Author 1: Bruria Haberman [email protected]
Author 2: Haim Averbuch [email protected]
Author 3: David Ginat [email protected]
Article Link:
http://portal.acm.org/citation.cfm?id=1067469&coll=ACM&dl=ACM&CFID=72174581&CFTOKEN=78331598