This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Construction and Preliminary Validation of a Dynamic Programming Concept Inventory

\nameMatthew Ferlanda, Varun Nagaraj Raob, Arushi Arorac, Drew van der Poelf, Michael Luuc, Randy Huynhc, Freddy Reiberd, Sandra Ossmanc, Seth Poulsene, Michael Shindlerc a University of Southern California, b Princeton University, c University of California Irvine,d Boston University, e Utah State University, f Northeastern University
keywords:
dynamic programming; algorithms education; concept inventory

1 Discussion

1.1 Overall Question Quality

Overall, our questions performed well with 9 out of the 15 misconceptions being selected by 40% or more of the students. However, as the results indicated, DV13 and DV14.2 continued to perform poorly even after revisions. Consequently, we removed these questions from the concept inventory, as they proved to be outliers.

1.2 Evidence that the Misconceptions Are Measured by the Questions

Misconceptions chosen by 15% or more of the students provide strong evidence that the misconception both targets and accurately measures the intended misunderstanding, thus validating our hypothesis about its prevalence. Highly prevelant misconceptions were:

  • •

    Misconception 2: DP always involves minimization or maximization

  • •

    Misconception 5: Conflating recursion with DP

  • •

    Misconception 7: Aspects of greedy problems are mistakenly associated with DP

  • •

    Misconception 8: Ignoring specific subproblems (and knowing which ones to solve)

  • •

    Misconception 11: Every problem has an efficient DP solution

  • •

    Misconception 13: DP involves tracking aspects of state to remember how a solution was constructed

Low-prevalence misconceptions (less than 15%) may suggest questions that fail to present the misconception clearly, or that our hypothesized misconception is less widespread than anticipated. Low-prevalence misconceptions were:

  • •

    Misconception 1: 2D DP solutions always traverse top left to bottom right

  • •

    Misconception 3: If a problem has minimization or maximization, it must be possible to efficiently solve it with DP

  • •

    Misconceptions 4: If a problem has minimization or maximization, there is no DP solution for it

  • •

    Misconception 14: DP always requires a 2D array

  • •

    Misconceptions 15: DP requires nested for loops, with the inner loop solving a recurrence

By analyzing selection rates across all categories, we evaluate each question’s construct validity, assessing its ability to measure the intended misconception genuinely. This analysis helps guide refinements to ensure our concept inventory reliably identifies and distinguishes between various misconceptions.

Appendix A I mostly use appendix in the draft for notes as we go

Appendix B Todo List

  1. 1.

    Provide a better title, since validation implies we have something in the process. Maybe something like “Validation of Question and Answer choices”