Student Misconceptions of Dynamic Programming
Shamama Zehra, Aishwarya Ramanathan, Larry Yueli Zhang, Daniel Zingaro · 2018
Dynamic Programming (DP) is considered to be one of the most difficult topics for students to understand in theoretical CS. Prior work suggests that misconceptions arise even when students have completed a course in which there is considerable focus on learning how to solve DP problems. We conducted think-aloud interviews with students who have completed the DP portion of the Algorithms course at a top North American research university. We report on three themes and their misconceptions discovered through this process. The first theme delves into students' struggles defining the notion of a subproblem and identifying particular subproblems. The second theme focuses on the understanding and usage of DP solution techniques compared to other algorithmic approaches. The third theme is composed of misconceptions related to defining and using recurrences. Analysis of each misconception provides insight into student thinking and offers ideas for improving the education of DP to university students.