title: Towards Algorithm Comprehension
Creators: name: Kather, Philipp
Publisher: name: University of Muenster, Institutional Repository MIAMI
Year: 2024
Subjects: subject: 000 Computer science, information, general works
subject: 370 Education
subject: 620 Engineering and allied operations

description: Diese Arbeit befasst sich mit dem Verständnis von Algorithmen, die Probleme effizient lösen, und dem dazugehörigen Beweis der Eigenschaften dieser Algorithmen. Algorithmen werden als Prozess beschrieben, z.B. in Pseudocode, und durch eine Argumentationskette, die deren Eigenschaften beweist. Obwohl Algorithmen zentral in Forschung und Lehre sind, wurde ihr Verständnis bisher kaum untersucht. Ziel dieser Arbeit ist die Entwicklung einer Theorie zum Algorithmenverständnis, die als Grundlage für zukünftige Forschungsarbeiten dienen soll. Die hier vorgestllte Theorie beschreibt drei mentale Komponenten: das Verständnis des Prozesses, der Argumentationskette und der Domäne. Diese Komponenten interagieren auf unterschiedlichen Abstraktionsebenen und werden durch Faktoren wie Vorwissen beeinflusst.
description: This thesis focuses on understanding algorithms that efficiently solve specific problems, often accompanied by a proof or proof sketch demonstrating their properties. Algorithms are viewed as a process description (e.g., pseudocode) and a reasoning chain that justifies their correctness. Understanding such algorithms is crucial for advanced students with a foundation in programming and discrete mathematics. Despite the importance of algorithms, research on their comprehension has been limited. This thesis develops a theory of algorithm understanding, addressing gaps in existing theories on program and proof comprehension. The proposed theory outlines three interconnected mental components: understanding the process, reasoning chain, and domain, influenced by prior knowledge and materials.
description: 1 Introduction ..... 1
1.1 Goal of this Thesis ..... 1
1.2 Algorithms in Computing Education Research ..... 3
1.3 Relation to Previously Published Work and Outline ..... 15
I Program Comprehension as a Base for Algorithm Comprehension ..... 17
2 Program Comprehension Research ..... 21
2.1 Definition of Program Comprehension ..... 22
2.2 Application of Program Comprehension ..... 23
2.3 Parameters of Program Comprehension Studies ..... 25
2.4 Program Comprehension Models ..... 26
2.5 Factors Complicating Comprehension ..... 33
2.6 Schemata, Plans and Plan-Composition ..... 35
2.7 Eye-tracking in Program Comprehension Research ..... 38
3 Exploring Factors of Program Comprehension in Algorithm Comprehension ..... 43
3.1 Research Questions ..... 43
3.2 Methodology ..... 44
3.3 Results of the Quantitative Analysis ..... 64
3.4 Qualitative Analysis ..... 72
3.5 Discussion of Qualitative and Quantitative Results ..... 81
3.6 Threats to Validity ..... 82
3.7 Conclusion ..... 89
II Aspects of Algorithm Comprehension ..... 91
4 Proof Comprehension ..... 95
4.1 Definition of Proof Comprehension ..... 95
4.2 Application of Proof Comprehension ..... 97
4.3 Proof Comprehension Models ..... 98
5 Connections between Code and Chain of Reasoning ..... 103
5.1 Methodology ..... 103
5.2 Results ..... 104
5.3 Discussion of Findings ..... 107
5.4 Summary ..... 115
6 Contrasting Algorithm and Program Comprehension ..... 119
6.1 Methodology ..... 119
6.2 Material ..... 124
6.3 Participants ..... 129
6.4 Findings and Discussion ..... 129
6.5 Summary ..... 140
III Towards a Theory of Algorithm Comprehension ..... 143
7 Towards a Theory of Algorithm Comprehension ..... 149
7.1 Core Category ..... 149
7.2 Methodology ..... 151
7.3 Discussion of Findings ..... 155
7.4 Threats to Validity ..... 172
8 Model of Algorithm Comprehension ..... 175
8.1 Algorithm Comprehension Model ..... 175
8.2 Related Work and Further Research ..... 179
8.3 Implications for Educators ..... 188
8.4 Conclusion and Outlook ..... 193
Bibliography ..... 195
A Example Appendix ..... 215
A.1 Transcription and Anonymization ..... 215
A.2 Interview Guide Line for Advanced participants ..... 215
A.3 Interview Guide for the Think Aloud Interviews ..... 218
A.4 Screenshots of the Eye-Tracking Application ..... 227
Curriculum Vitae ..... 239