Benchmarking Partial Credit Grading Algorithms for Proof Blocks Problems

Proof Blocks (proofblocks.org ) is a software tool that allows students to practice writing mathematical proofs by dragging and dropping lines instead of writing proofs from scratch. Because of the large solution space, it is computationally expensive to calculate the difference between an incorrect student solution and some correct solution, restricting the ability to automatically assign students partial credit. We benchmark a novel algorithm for finding the edit distance from an arbitrary student submission to some correct solution of a Proof Blocks problem on thousands of student submissions, showing that our novel algorithm can perform over 100 times better than the naïve algorithm on real data. Our new algorithm has further applications in grading Parson’s Problems, task planning problems, and any other kind of homework or exam problem where the solution space may be modeled as a directed acyclic graph.