Automated feedback generation in introductory programming education : a dynamic program analysis approach

Abstract

Anyone who ever manually corrected or graded any type of student assignment is aware of how tedious, error-prone and time-consuming this task is. In the context of programming assignments the situation is even worse: with a rising demand for programming education there are online courses with thousands of students, which makes manual grading downright impossible. However, students who are learning programming, especially at the introductory level, are in pressing need of guidance. This has motivated a lot of research on computer-aided feedback generation in introductory programming education. Many of these approaches are based on practices and methods employed in software engineering, testing, and verification, such as: code reviews, debugging, automated test generation, program synthesis, program repair, ... This is very useful feedback as it mimics how software engineers reason about the code. However, there are still numerous open issues. In this thesis, we will address the following two challenges: Most of the existing research focused on generating functional feedback, that is, to help the students write any correct program, while ignoring non-functional properties such as e.g., performance. Most of the existing approaches lack some of the following desirable properties: automation (require as little manual effort as possible), correctness (generate correct feedback), performance (generate feed-back in order of seconds), exhaustiveness (generate feedback for most student programs), and usefulness (reduce the teacher effort or help the student to make progress). We first study inefficient (but correct) student programs in order to understand the performance problems faced by students in introductory programming. From the study we observe that in order to provide feedback we need to identify the high-level algorithmic strategy used by the student's program, while ignoring its low-level implementation details. To that end we propose a lightweight specification language that enables the teacher to specify various algorithmic strategies, and a novel dynamic program analysis to determine whether a student's attempt matches the teacher's specification. To provide feedback on (functional) correctness of student programs we propose a novel fully-automated program repair algorithm that uses the wisdom of the crowd: it leverages the existing correct student solutions to syntactically modify incorrect student attempts. The repair algorithm builds on and extends our earlier dynamic program analysis in order to determine whether a modified (repaired) program has the same behavior as a correct solution. We have implemented both of the proposed approaches in practical tools and performed an experimental evaluation on a large number of student attempts from various programming courses. We have evaluated both of our approaches on the above mentioned desirable properties: automation, correctness, performance, exhaustiveness, and usefulness.