How Do Learners Use Scratch Paper When Working on Dynamic Programming Problems?

Dynamic programming (DP) is one of the most challenging topics in algorithms courses. Although there exist animation tools that assist with the understanding of DP algorithms, few existing tools are aimed at scaffolding the process of solving DP algorithm design problems. To help create a learning tool able to provide the affordances learners need when attempting DP problems, we analyzed learners' scratch paper to understand how learners approach DP problems. Based on scratch paper from 18 learners solving DP problems during a think-aloud study, we created a codebook that characterized different elements and methods used by the learners on their scratch paper. We found that learners had distinct preferences when attempting DP problems. Some learners preferred using example input with specific values to simulate ideal program executions, while some used math representations of example inputs to help derive formulas. Learners interacted with their example input in multiple ways, including filling in hand-drawn tables to organize the calculation process and dynamically interacting with the inputs by crossing, circling, or using arrows to visualize the relationships between inputs. These findings suggest potential interactions that need to be taken into consideration when designing tools to support learners in solving DP problems.