Exploring Traces from Algorithm Simulation: Students' Conceptions of Dijkstra's Algorithm

This full research paper explores undergraduate students' misconceptions of Dijkstra's algorithm quantitatively. Graph algorithm misconceptions have been studied to a modest extent, but they support effective instruction. A visual algorithm simulation (VAS) exercise requires a student to trace the algorithm by modifying a data structure visualization. We investigated effective ways to mine new algorithm misconceptions from VAS exercise data. In addition, we searched for previously unknown misconceptions of Dijkstra's algorithm. Students simulated Dijkstra's algorithm with a VAS exercise by adding edges of a given graph to a spanning tree. The simulations produced execution patterns which were mapped into a canonical form. We constructed another graph representing exercise states in all simulations. Using an interactive visualization of the state graph, we built hypotheses for misconceptions. The hypotheses were modeled as algorithms whose execution patterns were matched against students' simulations to find frequency of the hypothetical misconceptions. Pattern matching indicated that certain simulations resembled depth-first search, breadth-first search, and Prim's algorithm. Other simulations had evidence that students had understood the purpose of Dijkstra's algorithm, but arrived to the correct solution with ad hoc heuristics. The findings demonstrate how a VAS exercise was designed to reveal students' difficulties with graph algorithms. The methodology supports recognizing common misconceptions and therefore giving automated, formative feedback. The misconceptions itself are applicable to any exercise on elementary graph algorithms. Interactive visualization of an exercise state graph demonstrates the use of a new data-driven method for eliciting misconceptions.