CASET: Complexity Analysis using Simple Execution Traces for CS* submissions
This addresses a tedious grading challenge for CS educators by automating algorithm identification, though it is incremental as it builds on existing auto-grading methods.
The paper tackles the problem of automatically grading student submissions in CS1/CS2 courses when correctness depends on the algorithm used, not just output, by proposing CASET, a tool that analyzes time complexity using dynamic traces and unsupervised machine learning to classify submissions into complexity baskets, showing effectiveness on algorithms like sorting and dynamic programming.
The most common method to auto-grade a student's submission in a CS1 or a CS2 course is to run it against a pre-defined test suite and compare the results against reference results. However, this technique cannot be used if the correctness of the solution goes beyond simple output, such as the algorithm used to obtain the result. There is no convenient method for the graders to identify the kind of algorithm used in solving a problem. They must read the source code and understand the algorithm implemented and its features, which makes the process tedious. We propose CASET(Complexity Analysis using Simple Execution Traces), a novel tool to analyze the time complexity of algorithms using dynamic traces and unsupervised machine learning. CASET makes it convenient for tutors to classify the submissions for a program into time complexity baskets. Thus, tutors can identify the algorithms used by the submissions without necessarily going through the code written by the students. CASET's analysis can be used to improve grading and provide detailed feedback for submissions that try to match the results without a proper algorithm, for example, hard-coding a binary result, pattern-matching the visible or common inputs. We show the effectiveness of CASET by computing the time complexity of many classes of algorithms like sorting, searching and those using dynamic programming paradigm.