Efficient Feedback and Partial Credit Grading for Proof Blocks Problems

Seth Poulsen, Shubhang Kulkarni, Geoffrey Herman, Matthew West

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationArtificial Intelligence in Education - 24th International Conference, AIED 2023, Proceedings
EditorsNing Wang, Genaro Rebolledo-Mendez, Noboru Matsuda, Olga C. Santos, Vania Dimitrova
Number of pages13
ISBN (Print)9783031362712
StatePublished - 2023
Event24th International Conference on Artificial Intelligence in Education, AIED 2023 - Tokyo, Japan
Duration: Jul 3 2023Jul 7 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13916 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Artificial Intelligence in Education, AIED 2023


  • Automated feedback
  • Mathematical proofs
  • Scaffolding

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient Feedback and Partial Credit Grading for Proof Blocks Problems'. Together they form a unique fingerprint.

Cite this