  Proof Blocks is a software tool that allows students to practice writing
mathematical proofs by dragging and dropping lines instead of writing proofs
from scratch. Proof Blocks offers the capability of assigning partial credit
and providing solution quality feedback to students. This is done by computing
the edit distance from a student's submission to some predefined set of
solutions. In this work, we propose an algorithm for the edit distance problem
that significantly outperforms the baseline procedure of exhaustively
enumerating over the entire search space. Our algorithm relies on a reduction
to the minimum vertex cover problem. We benchmark our algorithm on thousands of
student submissions from multiple courses, showing that the baseline algorithm
is intractable, and that our proposed algorithm is critical to enable classroom
deployment. Our new algorithm has also been used for problems in many other
domains where the solution space can be modeled as a DAG, including but not
limited to Parsons Problems for writing code, helping students understand
packet ordering in networking protocols, and helping students sketch solution
steps for physics problems. Integrated into multiple learning management
systems, the algorithm serves thousands of students each year.
