Towards automatic advice in visual algorithm simulation

Thumbnail Image

Files

master_Tilanterä_Artturi_2020.pdf (2.16 MB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
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.

Authors

Date

2020-05-19

Department

Major/Subject

Computer Science

Mcode

SCI3042

Degree programme

Master’s Programme in Computer, Communication and Information Sciences

Language

en

Pages

85

Series

Abstract

Visual Algorithm Simulation (VAS) exercise is an interactive application, which teaches an algorithm or a data structure. The exercise shows the student a visual representation of a data structure with initial data. The student imitates the execution of the algorithm by interacting with the visual representation. The student's solution is graded automatically. A misconception about the algorithm being learned can manifest itself as systematic errors, which can be modelled as a new algorithm. It is assumed that a VAS exercise, which could detect automatically a misconception and give corrective feedback would further support learning. This thesis includes a literature review on algorithm misconceptions and an empirical study. Four VAS exercises of OpenDSA e-textbook are reviewed by their program code: Evaluating a postfix expression, Build heap, Quicksort, and Dijkstra's algorithm. A dataset of 1430 Build heap VAS submissions is analysed manually with ad-hoc software. The submissions are then automatically classified based on the misconceptions found. The main result extends the set of known misconceptions of the Build-heap VAS exercise. 52 percent of the submissions were correct, 17 percent were misconceptions and the rest 31 percent had a lo0gical explanation. 95 per cent of submissions classified as misconception have multiple explanations with heap size of 10. The thesis presents a Python software, which can automatically classify the known misconceptions. Theory on how to generate VAS inputs, which support detection of misconceptions is discussed. The theory is applied by improving the input generation of Dijkstra's algorithm exercise. The thesis concludes that studying misconceptions in the VAS exercises of OpenDSA currently requires exercise-dependent work. Not all OpenDSA VAS exercises record enough data for later analysis. Moreover, the player and analysis software must be written separately for each exercise. There is need to develop the OpenDSA related software libraries to produce detailed exercise recordings. It should be studied how the heap size in the Build-heap exercise affects detection of misconceptions.

Visuaalinen algoritmisimulaatiotehtävä (VAS-tehtävä) on vuorovaikutteinen sovellus, joka opettaa algoritmin tai tietorakenteen. Tehtävä näyttää opiskelijalle kuvan tietorakenteesta lähtödatalla. Opiskelija mukailee algoritmin suoritusta vuorovaikuttamalla kuvaesityksen kanssa. Opiskelijan ratkaisu arvostellaan automaattisesti. Väärinkäsitys VAS-tehtävässä on opiskelijan järjestelmällinen väärinymmärrys, joka voidaan kuvata algoritmilla. On oletus, että VAS-tehtävä, joka tunnistaisi automaattisesti väärinkäsityksen ja antaisi korjaavaa palautetta, tukisi oppimista entisestään. Tämä opinnäytetyö sisältää kirjallisuustutkimuksen algoritmien väärinkäsityksistä sekä empiirisen tutkimuksen. Sähköisen OpenDSA-kirjan neljä VAS-tehtävää on tutkittu niiden ohjelmakoodiltaan: Postfix-lausekkeen evaluointi, binäärikeon rakentaminen, pikajärjestäminen ja Dijkstran algoritmi. Tietoaineisto, jossa on 1430 tallennetta Binäärikeon rakentaminen -tehtävästä, on analysoitu käsin tätä varten kehitetyllä ohjelmalla. Tallenteet on sitten automaattisesti luokiteltu löydettyjen väärinkäsitysten perusteella. Työn päätulos laajentaa binäärikeon rakentaminen -tehtävän väärinkäsityksien joukkoa. 52 prosenttia tehtäväpalautuksista oli oikein, 17 prosenttia väärinkäsityksiä ja loput 31 prosenttia voidaan selittää loogisesti. 95 prosentilla niistä palautuksista, jotka luokiteltiin väärinkäsitykseksi, oli useampi yhtä hyvä selitys, kun keon koko oli 10. Työ esittää Python-ohjelman, joka voi automaattisesti luokitella tunnettuja väärinkäsityksiä. Työ esittää myös teoriaa, kuinka tuottaa VAS-tehtävien lähtödataa siten, että se tukisi väärinkäsitysten tunnistamista. Teoriaa on sovellettu parantam alla Dijkstran algoritmi -tehtävän syötteen tuottamista. Johtopäätöksenä OpenDSA:n VAS-tehtävien väärinkäsitysten tutkiminen vaatii nykyisellään tehtäväkohtaista työtä. Kaikki OpenDSA:n VAS-tehtävät eivät tallenna riittävästi dataa myöhempää analyysiä varten. Lisäksi tehtävätoistin ja analyysiohjelma pitää kirjoittaa erikseen joka tehtävälle. On tarve kehittää OpenDSA:n ohjelmakirjastoja tuottamaan yksityiskohtaisia tehtävätallenteita. Binäärikeon rakentaminen -tehtävässä pitäisi tutkia keon koon vaikutusta väärinkäsitysten tunnistamiseen.

Description

Supervisor

Korhonen, Ari

Thesis advisor

Seppälä, Otto

Keywords

computing education, algorithm visualisation, automatic assessment, misconception

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202005243300

Collections

[dipl] Perustieteiden korkeakoulu / SCI