aalto1 untyped-item.component.html
Exploring Traces From Algorithm Simulation : Students’ Conceptions of Dijkstra’s Algorithm
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
9
Series
2025 IEEE Frontiers in Education Conference (FIE), pp. 1-9, Conference proceedings : Frontiers in Education Conference
Abstract
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.
Description
Other note
Citation
Tilanterä, A, Korhonen, A, Seppälä, O, Taivainen, T & Croell, I 2025, Exploring Traces From Algorithm Simulation : Students’ Conceptions of Dijkstra’s Algorithm. in 2025 IEEE Frontiers in Education Conference (FIE). Conference proceedings : Frontiers in Education Conference, IEEE, pp. 1-9, Frontiers in Education Conference, Nashville, Tennessee, United States, 02/11/2025. https://doi.org/10.1109/FIE63693.2025.11328578