Benchmarking Partial Credit Grading Algorithms 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. 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.

Original languageEnglish (US)
Title of host publicationArtificial Intelligence in Education. Posters and Late Breaking Results, Workshops and Tutorials, Industry and Innovation Tracks, Practitioners’ and Doctoral Consortium - 23rd International Conference, AIED 2022, Proceedings
EditorsMaria Mercedes Rodrigo, Noburu Matsuda, Alexandra I. Cristea, Vania Dimitrova
Number of pages5
ISBN (Print)9783031116469
StatePublished - 2022
Event23rd International Conference on Artificial Intelligence in Education, AIED 2022 - Durham, United Kingdom
Duration: Jul 27 2022Jul 31 2022

Publication series

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


Conference23rd International Conference on Artificial Intelligence in Education, AIED 2022
Country/TerritoryUnited Kingdom


  • Automated feedback
  • Mathematical proofs
  • Scaffolding

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this