Automated Classification and Feedback Generation for Programming Assignments

Online-learning platforms (e.g., Coursera, Khan Academy, edX) are very popular and massive open online courses (MOOCs) have attracted thousands of students. We study the following reserach problem : in the traditional classroom setting students are given feedback (hints) by an instructor; in MOOCs this is not possible, since there typically is only a small number of instructors. For introductory programming assignments, students require feedback on different aspects of their code:

  1. Correctness: guidance for writing a correct program.
  2. Performance: help for improving the performance of an already correct program.

We have developed a tool that classifies student programs based on their high-level idea (which we also call algorithmic strategy); this classification enables us to automatically give feedback on correctness and performance: By recognizing the high-level idea of the student we can say “good job, your code is efficient!” or give a suggestion how to improve the code. Similarly, by recognizing the high-level idea of the student we can compare the student’s code to a correct program with the same high-level idea, and based on the differences suggest how to repair the program. Examples below illustrate these ideas:

Assignment: Decide if two strings (s and t) are anagrams (two strings are anagrams if they can be permuted to become equal).
bool Puzzle(string s, string t) {
  var sa = s.ToCharArray();
  var ta = t.ToCharArray();

  Array.Sort(sa);
  Array.Sort(ta);
  
  return sa.SequenceEqual(ta);
}
bool Puzzle(string s, string t) {
  return s.All(c =>
         s.Where(c2 => c2 == c)
          .Count()
         == t.Where(c2 =>c2 == c)
             .Count());
}
bool Puzzle(string s, string t) {
  if (s.Length != t.Length) return false;
  char[] sa = s.ToCharArray();
  char[] ta = t.ToCharArray();
  for (int j=0; j < sa.Length; j++) {
    for (int i=0; i < sa.Length - 1;i++) {
      if (sa[i] < sa[i+1]){
        char temp=sa[i];
        sa[i]=sa[i+1];
        sa[i+1]=temp;
      }
      if (ta[i] < ta[i+1]){
        char temp=ta[i];
        ta[i] = ta[i+1]; ta[i+1] = temp;
      }
    }
  }
  for (int k = 0; k < sa.Length; k++) {
    if (sa[k] != ta[k]) return false;
  }
  return true;
}
bool Puzzle(string s, string t) {
  if (s.Length != t.Length) return false;

  foreach (Char ch in s.ToCharArray()){
    if (countChars(s, ch) != countChars(t, ch)){
      return false;
    }
  }
  return true;
}

int countChars(String s, Char c){
  int number = 0;

  foreach (Char ch in s.ToCharArray()){
    if (ch == c){
      number++;
    }
  }
  return number;
}
Feedback: “Instead of sorting, compare the number of characters in strings”. Feedback: “Count the characters in a pre-processing phase, instead of in a loop”.

These four examples show correct, but inefficient programs (all have complexity O(n2), while there exists a solution with complexity O(n) — do you know what it is?). The programs on the right use a different high-level idea (aka algorithmic strategy) than the programs on the left (counting character occurences instead of sorting). Our tool classifies programs based on the used algorithm, and despite their syntactic differences gives the same feedback for the programs on the left resp. on the right.

Assignment: Read two integers 0 <= n <= m, and count the Fibonacci numbers in the closed interval [n,m].
int main() {
  long a=0, b=1,c=0,cnt=0;
  long int n,m;
  scanf("%ld%ld",&n,&m);
  while (c<=m) {
    c=a+b;
    if ((c>=n)&&(c<=m))
      cnt=cnt+1;
    a=b;
    b=c;
  }
  printf("%d",cnt);
}
int main() {
  long int n,m,f,n1=2,n2=3;
  int c=0;
  scanf("%ld %ld",&n,&m);
  while(f<=m) {
    f=n1+n2;
    n1=f; 
    n2=n1;
    if(f>=n && f<=m) c++;
  }
  printf("%d",c);
}
Correct program Incorrect program; feedback: "1. Assign 0 to n2 and f, and 1 to n1 before the loop; 2. Move the statement n2=n1; before n1=f; in the loop."
Our tool computes the smallest number of changes that transform the incorrect program on the right into the the correct program on the left, resulting in the feedback shown above. In fact, our tool computes such a repair with regard to every correct program in the database and reports only the repair that is best (smallest number of edits) with regard to all correct programs.

Classification and feedback generation is a very active area of research, and our goal is to develop techniques and tools to improve the state-of-the-art in automated programming education. If you find these results exciting, we can offer you a variety of topics for bachelor/master theses, projects for practical course work, and student jobs.

[Contact Florian Zuleger, Ivan Radiček]

For more information, also check our recent paper on this topic: Feedback Generation for Performance Problems in Introductory Programming Assignments.

Latest News

Helmut Veith Stipend

The first recipient of the Helmut Veith Stipend for excellent female master’s students in computer science will be presented on March 14 at the following event: "More female students in computer science. Who cares?" Panel discussion with renowned scientists about diversity in STEM Studies March 14, 5:30pm, TU Wien The Helmut Veith Stipend is dedicated […]

Continue reading

WAIT 2016 in Vienna

The third WAIT workshop on induction is held between 17-18 November at the TU Wien. Details are available on the workshop page.

Continue reading

Two papers at POPL’17

Two papers co-authored by researchers from our group have been accepted for POPL’17: “Coming to Terms with Quantified Reasoning” by Simon Robillard, Andrei Voronkov, and Laura Kovacs; and “A Short Counterexample Property for Safety and Liveness Verification of Fault-tolerant Distributed Algorithms” by Igor Konnov, Marijana Lazic, Helmut Veith, and Josef Widder

Continue reading

Helmut Veith Stipend

Outstanding female students in the field of computer science who pursue (or plan to pursue) one of the master‘s programs in Computer Science at TU Wien taught in English are invited to apply for the Helmut Veith Stipend

Continue reading

LogicLounge in memoriam Helmut Veith

Will robots take away your job? In memory of Helmut Veith, this year’s Conference on Computer Aided Verification (CAV), which takes place in Toronto, will feature a LogicLounge on the effect of automation and artificial intelligence on our jobs.

Continue reading

Full news archive