DPAssist: Automated Feedback Generation for Iterative Dynamic Programming Assignments

Authors: Shalini Kaleeswaran, Anirudh Santhiar, Aditya Kanade, Sumit Gulwani

Abstract:
Dynamic programming is a core algorithmic technique, taught com- monly in algorithms courses. While a powerful tool when mastered, students —who are learning it for the first time— may struggle with the decomposition of the problem into overlapping subproblems and iterative reuse of the solutions to the subproblems. In this paper, we present DPAssist, an automated technique to generate feedback on student submissions written using iterative dynamic programming strategy. DPAssist checks a student submission against reference implementations provided by the instructor. Checking program equivalence is difficult in this setting because of stylistic variations and use of procedures, loops and arrays. DPAssist therefore follows a novel staged approach. It performs a combination of static analysis and pattern matching on a program to compute a high-level, precise summary and then checks equivalence of summaries using an SMT solver. DPAssist identifies a reference implementation whose summary is closest to that of the student submission. If they are not equivalent, it reports a complete list of semantic differences between the two, using a novel counter-example guided iterative feedback generation algorithm. We have evaluated DPAssist on 518 programs submitted to two problems posed on a contest site. DPAssist generated correct feedback on 79.5% submissions in average 5.3s each. It required only one reference implementation for every 11 submissions. This shows that the staged approach of DPAssist successfully handles a multitude of stylistic variations in submissions without requiring proportionately many reference implementations.

pdf