Observations on Student Misconceptions--A Case Study of the Build-Heap Algorithm

Data structures and algorithms are core issues in computer programming. However, learning them is challenging for most students and many of them have various types of misconceptions on how algorithms work. In this study, we discuss the problem of identifying misconceptions on the principles of how algorithms work. Our context is algorithm simulation exercises, where students simulate the steps of a given algorithm by manipulating data structure visualizations on a computer screen by using a mouse. Thus, contrasting to "typical" data structures and algorithms courses, these exercises are designed to work on an abstraction level higher than that of the actual implementation. We have analyzed the recorded simulation sequences to infer existing misconceptions from students' answers, and then implemented the corresponding variations of the target algorithm to find out how many of students' answers consistently follow each variation. The results suggest that many students are aware of the ultimate goal of the algorithm but have not studied the algorithm itself well enough. This often leads to different misconceptions that can be modeled and recognized using our approach. The results presented here concern the Build-Heap algorithm, but the approach is of general value. (Contains 1 figure, 1 table and 4 notes.)