|
Article Excerpt
This article presents research on students' understanding of basic concepts in Graph Theory. Students' understanding is analyzed through the lens of the theoretical framework of reducing abstraction (Hazzan, 1999). As it turns out, in spite of the relative simplicity of the concepts that are introduced in the introductory part of a traditional Graph Theory course, some students exhibit ways of thinking that indicate a reduction of the level of abstraction. The importance of this study is derived from the importance of graph algorithms in any computer science curriculum and the centrality of the concept of abstraction in computer science education.
INTRODUCTION
Graph Theory is one of the basic courses in any computer science curriculum. It "has long become recognized as one of the more useful mathematical subjects for the computer science student to master" (Even, 1979, p. V). In this article, the focus is placed on the introductory part of Graph Theory that addresses the following topics: basic definitions, different kinds of graphs and their properties, graph traversing, shortest paths, trees (binary trees, directed trees, spanning trees, ordered and positional trees) and flow in networks.
The concepts mentioned above are usually learned in an introductory Graph Theory course by mathematics and computer science undergraduate students. Depending on the student population, different aspects of the subject are emphasized. For example, in mathematics programs the theoretical aspects of Graph Theory may be emphasized whereas in computer science undergraduate programs it may be the algorithmic nature of Graph Theory that is emphasized. Naturally, a mixed approach can be adopted as well. This mixed approach is applied in the course that is addressed in this article (cf. Section 2--The Course).
This article analyzes undergraduate students' understanding of the above basic concepts of Graph Theory. The analysis is performed through the lens of reducing abstraction. The theme of reducing abstraction is a theoretical framework that has been used up to now for explaining student conception of different undergraduate mathematics and computer science topics, such as abstract algebra, computability and data structures topics (Hazzan, 1999, 2003A, 2003B). This framework suggests several mental processes, which can be interpreted as a reduction of the level of abstraction, that students employ unconsciously while trying to cope with problem solving situations. In this article, we illustrate the application of this framework with respect to students' conception of Graph Theory concepts by looking at two ways by which abstraction is reduced: process perception and specification. This theoretical framework of reducing abstraction is further elaborated in Section 3 in which the data is analyzed.
Section 1 describes the educational research that has been done so far on the learning and teaching of Graph Theory. Section 2 describes the background of our research. Section 3 examines the conception of Graph Theory through the theoretical framework of reducing abstraction. First, within the framework of the process-object duality, we illustrate student comprehension of concepts in Graph Theory as processes (as opposed to objects). Second, we illustrate student tendency to specify the concept with which they think either by considering a particular case when the situation they are faced with requires the consideration of a set of objects, or by relying on the visual aspect of graphs. Section 4 concludes with some pedagogical remarks and suggestions for future research.
SECTION 1 RESEARCH ABOUT THE TEACHING AND LEARNING OF GRAPH THEORY
According to our literature review, the community of computer science education research gives little attention to the analysis of students' understanding of concepts in Graph Theory. As our literature review reveals, most of the literature concerning the learning and teaching of Graph Theory deals with the development of visualization tools that aim at supporting the learning process (cf. for example Khuri & Holzapfel, 2001; Hansen, Tuinstra, Pisani, & McCann, 2003; Hamilton-Taylor & Kraemer, 2002; Baker, Biolen, Goodrich, Tamassia, & Stibel, 1999).
One research work that does analyze students' understanding of Graph Theory concepts is described in Dagdilelis and Satratzemi (1998). In this article, the authors divided students' difficulties in Graph Theory algorithms into three categories. The first category addresses difficulties related to the recognition of the details of a given algorithm. More specifically, even in cases in which students exhibit an understanding of how an algorithm works in general and are able to follow a schematic representation of its application on a graph, they may face difficulties in understanding the details of the algorithm (1). The second category addresses students' difficulties in understanding the meaning of the intermediate stages and the results of an algorithm. The third category looks into the difficulties caused by the complexity of the programming languages used for the implementation of graph algorithms. The authors note that common programming languages are not suitably designed for the implementation of graph algorithms, and are not suited to the simplicity and shortness that characterize some of the graph algorithms. In other words, while the execution of some Graph Theory algorithms is trivial when done by hand, their execution becomes complex when expressed in terms of a programming language.
We find it interesting to explore student conception of Graph Theory for several reasons. First, the basic definitions in Graph Theory are quite simple. One reason for this is that, unlike groups (introduced to students in abstract algebra courses) or recursive languages (learned in computability courses), for example, graphs can be easily visualized. However, as it turns out and illustrated in Section 3, it may be the relative simplicity of the introductory part of Graph Theory that enables us to identify subtle observations in student conception of the relevant concepts. Second, algorithms play a central role in this course. In a similar way to the concept of function, algorithms have a dual nature. On...
|
