Skip to content

Experience in CS2040S

We share our experience of deploying the ITS in CS2040S during the spring semester of the 2023-2024 academic year.

Setup

CS2040S focuses on teaching data structures and algorithms. This course covers important data structure topics such as arrays, linked lists, stacks, queues, trees, graphs, sorting and searching algorithms, and algorithm analysis. The course is divided into seven weekly problem set, each focusing on a specific data structure or algorithm. The Intelligent Tutoring System is delivered as a web browser plugin that integrates with the Coursemology platform. Unlike CS1010S that we only show ITS feedback to human tutors to support their manual feedback drafting efforts, in CS2040S, we enabled the ITS feedback to be visible to students. We released the ITS feature to students in the middle of the semester to collect feedback on the usefulness of the system.

  • We enabled ITS for four problem sets of the second half of the semester. These tasks include Scapegoat Tree, Game Tree, Trie, and Graph Traversal.
  • The students can access the ITS generated feedback only if they have finalised submission and failed the pre-defined test cases. The feedback here is used as immediate feedback to supplement the often delayed feedback from human tutors. In total, there are 1058 incorrect submissions in the four problem sets.
  • Correct submissions in this semesters were also used as reference solutions to enhance the alignment component of ITS.

In addition to the in-class setup, we also conducted a controlled experiment of solving four LeetCode tasks among 30 students at the end of the semester to evaluate ITS's impact on their learning experience. We selected two programming tasks relevant to Tree and two programming tasks relevant to Graph, which are two very important data structure topics, both tasks are taken from LeetCode with similar difficulty and the required programming concepts are closely related to weekly problem sets. The four tasks are:

Tree Topic: We assess students’ understanding of Binary Search Tree definition and Pre/In/Post Tree Traversal, which is covered in Problem Set 4 of CS2040S.

Graph Topic: We assess students’ understanding of the Shortest-Path Problem in Graph, which is covered in Problem Set 8 of CS2040S.

We equally divided the 30 student participants into two groups:

  • Group A with access to ITS feedback for Task 1 and 3 (after finalise submissions).
  • Group B without access to ITS feedback for all four tasks.

Goal: We hypothesis that the students in group A should perform better than students in group B for Task 2 and Task 4 even without ITS. If the feedback they have received on Task 1 and Task 3 have strengthened their conceptual understanding of the topic.

The students were given 25 minutes to solve each task, after which they should move to the next task.

Experiment Results

Figure 1: Comparison of Correct Submissions on the Four Tasks.

Figure 1 reports the number of final correct submissions for each task. For task 1 and task 3, the group A and group B both do not have access to ITS feedback at the beginning, and the number of correct submissions are thus similar in both groups (Task 1: 6 vs 5, Task 3: 3 vs 4).
During the gap between Task 1, 2 and Task 3, 4, we presented the ITS feedback to group A students whose final submissions are incorrect. This leads to a substantial increase in the number of correct submissions for Task 2 and Task 4 in group A compared to group B. For group A, 4 out of 9 students who failed Task 1 successfully passed Task 2, and 5 out of 12 students who failed Task 3 successfully passed Task 4. For group B, only 2 out of 10 students who failed Task 1 successfully passed Task 2, and only 2 out of 11 students who failed Task 3 successfully passed Task 4.
Despite there might be some students solved successor tasks because they got additional time to work on a similar task, the improvement difference between group A and group B indicates the positive impact of ITS feedback on students' learning experience.

Case Study

We present one case study of a group B student who was almost correct, but in the end failed Task 1 and Task 2. The student's submission for Task 1 is explained in Data Structure Demo, and we show the student's submissions below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Example Student Submission for Task 1 (Incorrect)
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length <= 0 || inorder.length <= 0) {
        return null;
    }
    if (preorder.length != inorder.length) {
        return null;
    }

    return build(preorder, inorder, 0, inorder.length - 1);
}

public int index = 0;
private TreeNode build(int[] preorder, int[] inorder, int low, int high) {
    if (high < low) {
        return null;
    }

    TreeNode root = new TreeNode(preorder[index]);

    if (high == low) {
        return root;
    }

    int mid = -1;
    for (int i = low; i <= high; i++) {
        if (inorder[i] == preorder[index]) {
            mid = i;
            break;
        }
    }
    index++;
    TreeNode left = build(preorder, inorder, low, mid - 1);
    TreeNode right = build(preorder, inorder, mid + 1, high);
    root.left = left;
    root.right = right;

    return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# # Example Student Submission for Task 2 (Incorrect)
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder.length <= 0 || postorder.length <= 0 || 
        inorder.length != postorder.length) {
        return null;
    }

    if (inorder.length == 1) {
        return new TreeNode(inorder[0]);
    }

    return build(postorder, inorder, 0, inorder.length - 1);
}

public int index = 0;
private TreeNode build(int[] postorder, int[] inorder, int low, int high) {
    if (high < low || curr < 0) {
        return null;
    }

    TreeNode root = new TreeNode(postorder[index]);

    if (high == low) {
        return root;
    }

    int mid = -1;
    for (int i = low; i <= high; i++) {
        if (inorder[i] == postorder[index]) {
            mid = i;
            break;
        }
    }
    index++;
    TreeNode left = build(postorder, inorder, mid + 1, high);
    TreeNode right = build(postorder, inorder, low, mid - 1);
    root.left = left;
    root.right = right;

    return root;
}

The student submitted 8 attempts for task 1 and reached an almost correct solution which only needs a last mile repair to remove the redundant condition if (high == low) in the build helper method. Ideally, the student is expected to solve task 2 in the additional 25 minutes since the two tasks are isomorphic.

However, the student started with an task 1 identical solution in task 2 and later submitted 13 attempts, and none of them touch the erroneous condition. This example further demonstrates how struggling student can be even they are close to the correct solution and highlight the importance of immediate feedback. Interestingly, after we presented the feedback shown in below, the student immediately realized his mistake and successfully rectified the error in both Task 1 and Task 2.

ITS Feedback:

  1. Mistake on Termination Condition: This submission prematurely skips the recursive calls and returns the root node before the subtrees are properly constructed. By returning prematurely, the build function does not explore the entire preorder or inorder arrays, leading to an incomplete tree construction.