Ela Zur
Detecting
difficulties in acquiring
the concept: 'algorithm efficiency'
Introduction
The concept of
an algorithm's or program's efficiency is central in computer science (Harel,
1991). Hence, the concept of a program's efficiency has a central place in
computer science curricula of universities worldwide (Tucker et al., 1993;
Merrit et al., 1993).
In
A misconception
occurs when a person conceives a certain concept incorrectly or
unrealistically. Educators are very interested in the issue of misconceptions
and in recent years several studies have been published on the common
misconceptions of computer science students, especially with regard to
programming. Misconceptions were discovered in the main components of
programming languages: program, variable, assignment, input, output, etc.
(Bayman & Mayer, 1983; Stemler, 1989; Nachmias et al., 1990).
The
professional literature deals with possible reasons for the generation of
misconceptions and with ways of preventing them (Du Boulay, 1986; Saj-Nicloe &
Soloway, 1986).
In our research
we focused on misconceptions concerning an algorithm's efficiency, and the
causes for them among high school students. In addition, we examined whether
10th grade students are able to internalize this concept.
The Research Questions
1. What difficulties do students have in
understanding the concept of a program's efficiency?
2. To what extent do 10th grade students
succeed in internalizing the concept of a program's efficiency?
3. To what extent do 10th grade students
succeed in analyzing the algorithmic problem in a way that enables them to
write an efficient algorithm for solving the problem?
4. To what extent can students discern what
algorithmic problems require the use of arrays and what do not?
5. Is there a difference in mastery of
"Fundamentals of Computer Science" between 10th grade students taking
four study units in mathematics, and students taking five study units in
mathematics?
6. Is there a difference in mastery of
"Fundamentals of Computer Science" between boys and girls?
Research Method
Research
population – The research was conducted during the 1997-98 and 1998-99 school
years, at five schools that participated in an experiment, i.e., teaching
"Fundamentals of Computer Science" according to the new study
curriculum.
The
participants were:
174 10th grade students who had completed the study of Chapter 7 –
Iteration in "Fundamentals of Computer Science 1", and had not begun
Chapter 8 – The Efficiency of Algorithms in "Fundamentals of Computer
Science 1".
141 students at the end of the 10th grade, after completing the study of
"Fundamentals of Computer Science 1".
145 11th grade students who had completed the study of "Fundamentals
of Computer Science 2".
Research tools – The research
tools were three questionnaires. All questions were multiple choice questions,
and some asked for an explanation as well.
Questionnaire 1
contained questions about students' intuitions with regard to the concept of an
algorithm's efficiency, before learning about the concept in class (Chapter 8
in the textbook).
Questionnaire 2
contained questions about students' intuitions and misconceptions with regard
to the concept of an algorithm's efficiency, after studying and internalizing
the subject in class, that is after completing the
study of "Fundamentals of Computer Science 1" (Chapter 11 in the
textbook).
Questionnaire 3
contained questions about students' intuitions and misconceptions with regard
to the concept of an algorithm's efficiency, after completing the study of
"Fundamentals of Computer Science 2" in 11th grade.
Research
procedure - The students studied the study unit "Fundamentals of Computer
Science 1" in 10th grade. They responded to Questionnaire 1 before
studying Chapter 8, which deals with the efficiency of algorithms (and after
studying Chapter 7 – Iteration). The aim of Questionnaire 1 was to examine what
the students thought of the concept of an algorithm's efficiency before
learning about it in class. The students responded to Questionnaire 2, designed
to examine their understanding of the concept of an algorithm's efficiency,
after completing the "Fundamentals of Computer Science 1" study
program, namely after completing Chapter 11. The students had had time to
internalize the concept of an algorithm's efficiency, because some time had
passed between studying Chapter 8 (on the efficiency of algorithms) and Chapter
11.
In 11th grade,
only students who had elected to do so went on studying "Fundamentals of
Computer Science 2". The students responded to Questionnaire 3 after
completing the study of "Fundamentals of Computer Science 2". The aim
of Questionnaire 3 was to examine students' understanding of the concept of an
algorithm's efficiency after completing the study of "Fundamentals of
Computer Science 2". Another goal was comparing the development of concept
understanding over time, from 10th through 11th grade.
Findings and Conclusions
Misconceptions
Misconceptions
matching the intuitive rules: More A more B, same A same B.
A short program
(in terms of code lines) is more efficient than a long program; Two programs of identical length containing identical
instructions (but in a different order) are equally efficient. A program
containing more sentences in a loop is more efficient.
Misconceptions
possibly arising from being unacquainted with the "machine model":
A
program containing fewer variables is more efficient in terms of execution time.
A program containing a procedure is more
efficient than a program that does not contain a procedure.
Misconceptions
related to a combination of several factors:
A recursive program is more efficient
than an iterative program.
There
is no connection between the order of values in the input and the efficiency.
Misconceptions
indicating lack of understanding of the need for a concept of program
efficiency:
Two programs are equally efficient if
they perform the same task. Performance
time measured by clock is a measure for a program's efficiency.
Internalizing
the concept of program
efficiency in the 10th grade
Most 10th
graders are unable to internalize the concept of a program's efficiency, and an
intuitive concept is preserved in spite of the learning process.
Difficulties in
writing an efficient program
The percentage
of students who succeed in performing a mathematical analysis of the
algorithmic problem, and in writing an efficient
solution based on this analysis, is very small in Questionnaires 1 and 2 but
rises considerably in Questionnaire 3.
Arrays –
efficiency with regard to memory
In simple
algorithmic problems, most students (over 75%) are able to discern which
algorithmic problems require an array and which do not. When the algorithmic
problems are complex, a small percentage of the students (about 40%) are able
to discern whether an array is needed. Most tend to say an array is needed even
when it is not.
Most students
(about 75%) see the connection between the order of appearance of the values in
the input and the need for an array for solving the algorithmic problem.
Comparing the
knowledge of students taking five study units in mathematics with that of
students taking four study units
There was a
significant difference (Pvalue = 0.0027) on the average between students taking
five study units in mathematics and students taking four study units in
mathematics.
Difference
between the knowledge of boys and girls
No significant
difference was found in the 10th and 11th grades, between the knowledge of boys
and girls regarding "Fundamentals of Computer Science" (In
Questionnaire 1: Pvalue = 0.6534, in Questionnaire 2: Pvalue = 0.0611, in
Questionnaire 3: Pvalue = 0.2378).
* Pending final approval