Student misconceptions of dynamic programming: a replication study

ABSTRACT

Background and Context

We replicated and expanded on previous work about how well students learn dynamic programming, a difficult topic for students in algorithms class. Their study interviewed a number of students at one university in a single term. We recruited a larger sample size of students, over several terms, in both large public and private universities as well as liberal arts colleges.

Objective

Our aim was to investigate whether the results of the previous work generalized to other universities and also to larger groups of students.

Method

We interviewed students who completed the relevant portions of their algorithms class, asking them to solve problems. We observed the students' problem solving process to glean insight into how students tackle these problems.

Findings

We found that students generally struggle in three ways, “technique selection,” ”recurrence building,” and “inefficient implementations.” We then explored these themes and specific misconceptions qualitatively. We observed that the misconceptions found by the previous work generalized to the larger sample of students.

Implications

Our findings demonstrate areas in which students struggle, paving way for better algorithms education by means of identifying areas of common weakness to draw the focus of instructors.

KEYWORDS:

• Replication study
• dynamic programming
• algorithms education

Acknowledgments

We would like to thank Leo Porter, who first introduced Michael to the notions of concept inventories and to research about them in computer science. Professor Porter also helped our initial understanding of the area by providing references and introductions to other researchers doing work in the field. When we decided to build on the work of Zehra et al. (2018), we were introduced to Shamama Zehra, Aishwarya Ramanathan, Larry Yueli Zhang, and Daniel Zingaro, who we would also like to thank; their help in understanding the methodology behind their paper was extremely valuable. We also thank Jan Vahrenhold for helpful discussions. We thank the students who participated in this study and their professors who helped us with recruitment.

We also thank UCI’s Academic Senate Council on Research, Computing and Libraries (CORCL) for the research fund that enabled us to provide gift cards as incentives for participants.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Question 1, Coin Row

There is a row of n coins whose values are positive integers c1, c2, …, cn. The goal is to pick up the maximum-value coins such that you never pick up two adjacent coins. Your solution should be feasible for input of size n = 1000.

Example:

—

Input: [7, 15, 12]

Solution: 7 and 12 = 19

Input: [10, 4, 4, 10, 4, 4, 10]

Solution: 10 and 10 and 10 = 30

Question 2, Minimum Pixel Sum

Given an n by m 2D image where each pixel can be represented by a value that is 0 or 1, (where n is the number of rows and m is the number of columns) find the minimum sum of pixel values of a connected path of pixels. The path must begin somewhere in the first row of the image and end somewhere in the last row of the image, and each move can only go down or to the right.

$[1<=n<=1000][1<=m<=1000]$

Your solution should be feasible for input of size n times m = 100,000.

Example

—

Input:

$[[0,1],[1,0],[1,0]]$

Solution: Sum = 1. (0,0) - $>$ (0,1) - $>$ (1,1) - $>$ (2,1)

Input 2:

$[[1,0,1,0],[0,0,0,0],[0,1,0,1]]$

Solution: Sum = 0. (0,1) - $>$ (1,1) - $>$ (1,2) - $>$ (2,2)

Question 3, Consecutive 1ʹs

Design an algorithm to find the number of binary strings of length N that do not contain two consecutive 1ʹs. Your solution should be feasible for input of size N = 1000.

Example

—

Input: N = 3

Solution: 5

Explanation of Solution: [000] [001] [010] [100] [101] all work, but [110] [011] [111] do not

Question 4, Stock Market

Given a sequence of historical daily prices for a stock on n consecutive days, find the days on which someone should have bought the stock and then sold the stock so as to maximize earnings. On each day, you can do nothing, or buy the stock if you don’t own it, or sell the stock if you do own it.

Note: (Can only buy and sell once, and the “buy” day must be before the “sell” day)

Your solution should be feasible for input of size n = 1000.

Example

—

Input: [2, 5, 7, 1]

Solution: Buy on day 1, sell on day 3

—

Input: [5, 2, 4, 8, 5, 6, 7]

Solution: Buy on day 2, sell on day 4

Question 5, Peak-Finding

Given an array of n numbers that we know ascends up to some maximum value and then descends until the end of the array, find the maximum element of the array. Your solution should be feasible for input of size n = 1000.

Example

—

Input: [1, 3, 15, 17, 2]

Solution: 17

Notes

1. Based on the wording in Zehra et al. (2018), we assumed all final dynamic programming solutions were to be written iteratively.