Abstract
Personalized exercise recommendation is an important research project in the field of online learning, which can explore students’ strengths and weaknesses and tailor exercises for them. However, programming exercises differs from other disciplines or types of exercises due to the comprehensive of the exercises and the specificity of program debugging. In order to assist students in learning programming, this paper proposes a programming exercise recommendation algorithm based on knowledge structure tree (KSTER). Firstly, the algorithm provides a calculation method for quantifying students’ cognitive level to obtain their knowledge needs through individual learning-related data. Secondly, a knowledge structure tree is constructed based on the association relationship of knowledge points, and a learning objective prediction method is proposed by combining the knowledge needs and the knowledge structure tree to represent and update the learning objective. Finally, KSTER imports a matching operator that calculates cognitive level and exercise difficulty based on learning objectives, and makes top-η recommendation for exercises. Experiments show that the proposed algorithm significantly outperforms the other algorithms in both precision and recall. The comparison experiments with real-world data demonstrate that KSTER effectively improves students’ learning efficiency.
Introduction
Online learning has emerged as a product of combining new technology and education, providing a more flexible and convenient path for students to learn [1]. In programming learning, online learning has become a common way of learning. However, the programming skills of learners are mixed. How to efficiently and accurately recommend suitable exercises for students is of great significance to assisted learning. The exercises have a role in checking and remediating deficiencies for learners. Most of the existing research on exercise recommendation uses collaborative filtering (CF) [2] or cognitive diagnosis [3]. Collaborative filtering tends to ignore the differences in mastery of the exercises among students, and cognitive diagnosis can only model the learners’ mastery status of the examined knowledge points without fully considering the correlation of the knowledge points. The mastery of knowledge points is an important factor to measure the cognitive level of students, but it is not the only decisive factor. Therefore, it is still lack of accuracy and effectiveness to recommend exercises only through the state of knowledge.
Programming is a step-by-step process in which students’ learning objects are constantly updated. The process hides the students’ real weaknesses of knowledge, which need to be noticed and captured. However, programming exercises differs from other disciplines or types of exercises due to the comprehensive of the exercises and the specificity of program debugging. The programming exercise is a typical comprehensive exercise in programming learning, and each exercise contains one or more knowledge points. The knowledge point is not scattered individual, but has certain interrelated structural characteristics. If expert knowledge can be used to model the structure of knowledge points to form complex relationships among them, the efficiency of online learning for students can be improved. At the same time, the programming exercise contains one to more test points, and learners need to debug the program several times until the test points are fully passed before answering correctly. The learning objectives play a key role in the debugging of students’ programs. In addition, the cognitive level of students has an impact on learning effectiveness. When recommending exercises to students, it is necessary to consider whether the recommended exercises meet their cognitive level. Therefore, in addition to user preferences, programming exercise recommendation must consider two other issues, (1) whether the recommended exercises consider the connections between knowledge points, and (2) whether the recommended exercises meet the learners’ current learning objectives and cognitive level. In response to these problems, this paper proposes a personalized programming exercise recommendation algorithm based on knowledge structure tree. The algorithm is designed to adaptively recommend exercises for students based on his or her knowledge needs, learning objective and students’ answer preferences. First, a calculation method for quantifying the cognitive level of students is proposed to obtain the knowledge needs through the learning behavioral data of the student. Second, a knowledge structure tree for C programming is constructed by mining the correlations of knowledge points based on expert experience. Then a learning objective prediction method is proposed by determining and updating the learning objectives in conjunction with knowledge needs and knowledge structure tree. Final, a matching operator that calculates cognitive level and exercise difficulty is imported based on learning objectives, and the exercises are recommended by top-η.
Related work
There were many studies on personalized learning resource recommendation in online learning systems, including exercise recommendation [4], course recommendation [5], video recommendation [6] and so on. Personalized recommendation techniques become inevitable and essential to help learners choose wisely from the huge number of resources [7, 8]. Personalized recommendation plays a crucial role in online learning [9], and collaborative filtering is the most widely used method [10]. The method of grouping students helps to identify common characteristics of similar students, so that the recommended exercises are in line with the cognitive level of the students in the group. Segal deduced a group of students with similar learning behaviors to the target students through collaborative filtering, and recommended exercises to the target students according to the consensus reached by the group on the difficulty of the exercises [11]. Vukicevic used the idea of collaborative filtering to derive the predicted scores of all students on a test paper, and further divided students into three categories (poor, good, and excellent). And the system recommended exercises according to the students’ categories [12]. The most important thing in collaborative filtering is to estimate the behavioral preferences of new similar learners based on the behavior data of existing learners to recommend personalized learning resources for students. In [13], an ontology-based collaborative filtering recommendation algorithm is proposed, which can help users find the nearest neighbors and calculate the similarity of knowledge points for user ratings. However, the above recommendation methods based on collaborative filtering ignore the differences in the mastery of knowledge points among different students, and fail to model students from the perspective of cognitive attributes.
Most of the learning content navigation in existing systems is presented in text, which cannot fully display the structural relationship of knowledge points. This may affect learning efficiency. Knowledge points are the most direct measure of learners’ knowledge mastery, and can also directly reflect the gaps of learners. Therefore, knowledge points play a key role in achieving the goal of personalization and accuracy on recommendation. However, knowledge points are not independent individuals and are related to each other. Jiang proposed a personalized exercise recommendation algorithm based on knowledge hierarchy graph by constructing a weight graph that characterizes the hierarchical relationship of knowledge points (REKHG) [14]. Xia proposed a personalized recommendation algorithm that integrates learning objectives and assignment feedback by considering the coverage of knowledge points and the cognitive level of students (ER-LOAF) [15]. Zhu constructed a knowledge graph for computer network courses by analyzing the semantic relationships of knowledge, and proposed a personalized exercise recommendation method based on content and knowledge graph [16]. Most research efforts in assisted programming have focused on exercise recommendation. Researchers calculated the similarity of programming problems or learners based on the data from the online assessment system, and recommended programming exercise through collaborative filtering techniques [17, 18]. In a case study of C language teaching, firstly the label thinking is combined with modeling the relationship among learners, labels and exercises based on the learners’ historical record. Then, exercises are recommended according to the learner’s knowledge weaknesses [19]. The exercise recommendation system could recommend the suitable exercises for the learners according to the historical information records of their exercises [20]. In [21], a method for personalized recommendation of assignments (tasks or exercises) in an adaptive education system is proposed by considering the limited time for learning, learners’ cognitive level and the difficulty of the exercises.
Through the above analyses, scientific and rational knowledge representation can improve the quality of recommendation. The existing algorithms have generated favorable effects in personalized exercise recommendation, but it is not suitable for the recommendation of programming exercises. To this end, this paper proposes a programming exercise recommendation algorithm based on knowledge structure tree. In order to realize the personalization of online learning, three influencing factors are selected based on the structural correlation of knowledge points to improve the accuracy of recommendation and user satisfaction, including the grasp state of knowledge points, learning objectives and exercise difficulty.
The remainder of the paper is organized as follows. Section 3 introduces the personalized programming exercise recommendation algorithm based on knowledge structure tree. The comparison experiment is conducted to verify and evaluate the proposed algorithm in Section 4. Section 5 concludes the whole paper and presents our future work.
Proposed approach
The overall framework of KSTER
In this section, the technical route of the recommendation algorithm is introduced, and the overall framework of KSTER is shown in Fig. 1. The framework can recommend exercises to complete learning objectives and realize personalized learning. The main components contained in the framework include the following:

KSTER framework.
According to the individual learning behavior data, students’ learning characteristics are extracted to obtain quantitative cognitive level.
The knowledge structure tree is constructed by expert experience based on the relationship of knowledge points. It is integrated with the cognitive level to obtain the real knowledge needs of students. Learning objectives are represented and updated in relation to students’ knowledge needs and knowledge structure tree to obtain candidate exercises.
The recommendation module introduces the matching operator that calculates the students’ cognitive level and the difficulty of the exercise to get answer preferences of students. It focuses on the learner’s learning objective to recommend personalized exercises by his or her grasp state and answer preferences.
Cognitive level diagnosis
Achievement is an objective measure of the grasp state of knowledge points, and students’ cognitive level plays an important role in exercise recommendation. The cognitive level of students can be predicted in personalized recommendation based on their scores on the exercises. This paper recommends programming exercises in online learning. The programming exercise is different from other subjects or types of question. Each question has one to more test points and the student answers the question correctly only if the test points are fully passed. Students need to be compiled and debugged to get the correct answer. In programming learning, students can complete the exercises by debugging several times until they get a satisfactory score. Therefore, each student has a different number of program submissions on the same exercise. Students with a good learning base only need to submit a handful of times to achieve a full score. The number of program submissions in this paper is another factor that measures the grasp state of knowledge points.
Given a set U = (u1, u2, . . . , u
n
) of n students, the set of exercise score ratios is G = (G
u
1
, G
u
2
, . . . , G
u
n
), where G
u
i
= (g1, g2, . . . , g
M
). The exercise score is the ratio of the student’s actual score to the full score of the question, and its value is in [0, 1]. The number of student program submissions in this paper is counted only when there are no compilation errors and the test point is not fully passed. Students can receive a corresponding score for each submission. The ratio of the number of student submissions is defined as Equation (1).
Where H q denotes the total score of question q, λ u i represents the number of student submissions of the program on question q, and g u i a is the student’s score for each submission. s u i q denotes the rate of submission times. If the student u i has done v (v = 1, 2, . . . , M) exercises, then the number of submissions of the program on the question set is S u i = (s1, s2, . . . , s v ).
Each exercise consists of one or more knowledge points that are different from each other. Given M exercises, which consist of Z knowledge points. The set of exercises is Q = {q1, q2, . . . , q
M
}, the set of knowledge points is K = {k1, k2, . . . , k
z
}. The incidence matrix between the exercise and knowledge point is R = [r
mz
] M×Z. Where r
mz
= 1 means that exercise M examines the knowledge point Z; otherwise, r
mz
= 0.
Where v denotes the number of exercises.
(1) Construction of knowledge structure tree. The knowledge structure tree is a kind of knowledge organization and representation that decomposes knowledge into knowledge points of different granularities and organizes them with a tree structure. In programming learning, this paper uses knowledge points as indicators and constructs knowledge structure trees using the correlation relationships between knowledge points.
The knowledge point relationship can be divided into three categories: Prerequisite relation (Preorder). If knowledge point k
d
(d = 1, 2, . . . , Z) is a precursor to k
b
(b = 1, 2, . . . , Z), then k
d
must be learned before learning knowledge point k
b
. It is denoted as k
d
← k
b
. Inclusion relation (Suborder). Multiple sub-knowledge points are combined to form a composite knowledge point. If the composite knowledge point k
d
(d = 1, 2, . . . , Z) contains the meta-knowledge point k
b
(b = 1, 2, . . . , Z), then it is noted as k
d
⊇ k
b
. It means that k
b
is finer than k
d
. Parallel relation (Parallel). There is no necessary prerequisite or inclusion relationship between knowledge points k
d
and k
b
, but there is some connection in content or logic. It is noted as k
d
∼ k
b
.
In this paper, the knowledge structure tree of C programming is constructed based on expert experience (professors who have been teaching C programming for a long time) and textbook document data. Part of the knowledge structure tree is shown in Fig. 2. The root node is the knowledge structure of C programming, which contains 9 compound knowledge points. Each compound knowledge point contains several meta-knowledge points. There are 85 meta-knowledge points. There is an inclusion relationship between compound knowledge points and meta-knowledge points, and there are precursor and parallel relationships between some compound knowledge points. For example, the precursor knowledge point of “array” is “basic data type”. There are also precursor and parallel relationships between meta-knowledge points, such as the precursor of “function call” is “function definition and return value”.

Part of the knowledge structure tree.
(2) Prediction of knowledge needs. Learner’s learning behavior and state data are the key factors to realize personalized learning, and learner’s learning needs can be acquired by them [22]. In the knowledge structure tree, the parent-child relationship between nodes is reflected in the precursor and inclusion relationships. The root node is the first father node. It can be seen from the structure tree that the closer to the root node, the broader the range of knowledge points represented by the node. Conversely, the farther away from the root node, the finer the granularity of knowledge points. In order to better assist students in identifying specific weak knowledge points, the weights are calculated based on the correlations between knowledge points. The weight of nodes a and b are defined as:
Where parent (a, b) denotes the nearest common parent of nodes a and b, depth (parent (a, b)) denotes the path length from the nearest common parent to the root of the tree, and ds (a, b) is the average distance from nodes a and b to the root node of the tree. It can be expressed as:
This paper uses cognitive diagnostics to obtain students’ knowledge mastery levels, and the knowledge points are independent of each other. However, there are correlations between knowledge points in the real situation. In order to better portray students’ cognitive level, the correlation between knowledge points is introduced into cognitive diagnosis and students’ cognitive diagnosis result is updated, as shown in Equation (5).
Where L denotes the number of knowledge points in the precursor and inclusion relationship.
The status of knowledge can be divided into three levels, which are Complete Grasp, Basic Grasp and Fail Grasp. The rules of division are as in Equation (6). When the status of knowledge point is B or F, the knowledge point is added to the set of knowledge needs KN = {k1, k2, . . . , k
y
}, y ∈ [1, z].
Where
(3) Learning objective determination and its updating process. Learning objectives reflect the knowledge needs of students, and the determination of learning objectives depends on the change of the student’s knowledge state. The knowledge needs and the knowledge structure tree are used to obtain learning objectives. Learning objectives can be divided into learning objectives of meta-knowledge points and learning objectives of compound knowledge points based on the type of knowledge points and the relationship between knowledge points. Each knowledge point in the set of knowledge needs is mapped to the knowledge structure tree, and the learning objective is formalized as a set of knowledge points in the knowledge structure tree, denoted by KT = {k1, k2, . . . , k
x
}, x ∈ [1, y]. In the learning process, the knowledge points with the smallest value of knowledge mastery in the set of students’ knowledge needs are determined as the initial learning objectives of the student in turn. It can be defined as follows:
During the learning process, the target knowledge points are automatically updated by the learning state data until the initial learning objectives is completed. The completion of target knowledge points is mapped to the knowledge structure tree one by one, and the corresponding node is colored based on the grasp state of the knowledge. Complete Grasp and Basic Grasp are blue and gray respectively, and Fail Grasp is not colored. If the initial learning objective is a compound knowledge point, the grasp state of all compound and meta-knowledge points in the process of completing the objective is updated in the knowledge need set. If the initial learning objective is meta-knowledge points, the grasp state of all meta-knowledge points in the process is updated. The knowledge points with knowledge status B or F are retained and the set of student knowledge needs is updated. The personalized knowledge state diagram can be determined in the learning process. Figure 3 shows the process of learning objective updated.

Example of updating learning objective.
Figure 3(a) shows the knowledge state diagram of learners at a certain moment in the learning process, where a, b and c nodes are composite knowledge points. Nodes d to h are meta-knowledge points. Nodes d and e are blue and gray. From the above coloring rules, it is clear that the grasp state of d and e are respectively Complete Grasp and Basic Grasp. Algorithm 1 describes the inference algorithm for updating the learning objective.
When the student’s initial learning objective is c, the process of updating the learning objective is as follows: Firstly, direct prerequisite knowledge point b of c is found. By checking the state of b, it can see that the grasp state of b is Fail Grasp. The grasp state of d, e, and f nodes are checked through the inclusion and direct precursor relationships. It can be seen that the state of d is Complete Grasp, which meets the learning needs. But e and f need to be learned. Then, the learning objectives are updated to e and f. Learners are recommended exercises related to knowledge points e and f, and judge the grasp state of the knowledge point respectively. If the knowledge points are Complete Grasp, nodes e and f are colored blue, as shown in Fig. 3(b). Otherwise exercises related to the knowledge point are continued to be recommended. Next, the learning objective is updated to c, as shown in Fig. 3(c). According to the inclusion and direct precursor relationships, the next learning objective is updated to g and h. When the initial learning objective c is completed, then the grasp state of b to h is all Complete Grasp. The grasp state of b to h is updated. Finally, the set of students’ knowledge needs is updated to determine new initial learning objectives.
The learning objectives reflect the students’ learning needs. This paper helps students accomplish their learning objectives by recommending programming exercises to them. The use of exercises labeled with categories of knowledge points in programming learning can portray the grasp state of the knowledge points and thus determine the student’s learning objectives. The knowledge points in the learning objective set KT are intersected with the knowledge points of the exercises to obtain candidate knowledge points, and the exercises are filtered according to the candidate knowledge points to obtain the candidate exercise set.
The recommended exercises in personalized recommendations should be adapted to the cognitive level of learners as much as possible. It is difficult to show personalization by recommending exercises that are too difficult or too easy. Therefore, this paper matches the cognitive level of students with the difficulty of the exercises. If the difficulty of the question is more comparable to the students’ cognitive level, its matching value should be larger. Conversely, the smaller it should be. The matching degree calculation is formalized as:
Where
When the difficulty value is equal to the cognitive result, its value reaches the maximum value of 1. The larger the difference between the difficulty value and the cognitive result, the smaller the value will be. The exercises in the candidate set are ranked based on the magnitude of the match value, and are recommended by Top-η.
Where List (u i , q j ) denotes the final list of exercises recommendation, and η represents the maximum number of exercises recommended for a knowledge point.
Experiment datasets
The learning records of “C Programming” course in online programming system of Nanchang Hangkong University are used in the experiments. It can be divided into two parts: 1) A library of programming exercises labeled with knowledge points based on expert experience, involving 1386 programming exercises and 94 knowledge points. Each exercise contains 1 to 6 knowledge point labels. The difficulty of each programming question is labeled with a value belonging to the range [0, 1]. 2) The result dataset contains the answer records of 965 students by processing the abnormal and duplicate data. Table 1 shows the statistical information of the dataset.
Statistics of the dataset
Statistics of the dataset
In this experiment, the dataset is divided into two parts according to the proportion of 80% and 20%. The former is used as the training set to construct the recommendation model, while the latter is used as the test set. The cross-validation is used for 10 experiments, and the average value is taken as the experimental result. In the paper, precision, recall and F1 are used to measure the performance of the recommendation. Specifically, precision, recall and F1 are respectively defined as follows:
Where F u denotes the set of recommended exercises, and O u represents the set of exercises answered correctly by the learner u in the test set.
Choice of η
In this paper, the η can affect the performance of the recommendation algorithm. Figure 4 shows the change trend of η. With the increase of η, Precision decrease and Recall increase, indicating that the different values of η will directly affect the recommendation results of the algorithm. From the figure, the optimal value of at η= 5 is obtained on the dataset. The Precision and Recall are equal at η= 5, which ensures the recommendation performance and user satisfaction of KSTER.

The influence of parameter η on KSTER.
To comparatively evaluate the performance of our method, the following representative models are selected as comparison methods, including CF, REKHG, and ER-LOAF. The initial principles of the cognitive diagnostic models in KSTER, REKHG, and ER-LOAF are the same, which enables a more intuitive comparison of the performance of different recommendation algorithms. At the same time, CF is the benchmark in recommendation algorithms. It can be consistent with other methods in terms of cognitive diagnosis, and recommend exercises based on similarity between users. The proportion of exercises in the test set is set to 10%, 20%, 30% and 40%, and the comparison results of each algorithm on the dataset are shown in Fig. 5. It can be analyzed from the Fig. 5 that Precision, Recall and F1 values of CF algorithm on the dataset are much lower than those of the other three algorithm models, indicating that other algorithm models can effectively improve the recommendation accuracy of the recommendation algorithm. In addition, the KSTER algorithm outperforms the other three algorithms in Precision, Recall and F1, which proves that the proposed algorithm has a good effect on improving the recommendation accuracy.

Experimental results of different recommendation methods.
In order to understand the comparison effect of the experiment more intuitively, this paper presents the experimental results in the form of a table. Table 2 shows the Precision, Recall and F1 values of different algorithm when the exercise test proportion is different. It can be seen from the table that as the exercise test proportion changes, the values of Precision, Recall and F1 basically show a trend of increasing. The Precision and Recall values of the KSTER algorithm exceeded 74% and 43% respectively at 40% of the exercise test proportion, which were significantly higher than other algorithms. Compared with the CF algorithm, the Precision of REKHG, ER-LOAF, and KSTER in this paper are improved by 14.2%, 20% and 28.6%, respectively. Compared with the CF algorithm, the Recall of REKHG, ER-LOAF, and KSTER in this paper are improved by 6.2%, 12.3%, and 18.8%, respectively. This may be because the ER-LOAF method takes into account the correlation between students’ cognitive level and the difficulty of the exercises, making the probability of correct answers relatively higher. Although the REKHG algorithm considers the influence of hierarchical relationship of knowledge on students’ cognitive level, the correlation between knowledge are more complex than hierarchical structures. However, the KSTER in this paper not only correlates students’ cognitive level with the structure of knowledge points to determine learning objectives, but also updates learning objectives in real time according to students’ responses, and makes recommendation by combining learning objectives and exercise difficulty. KSTER is more accurate in targeting students’ weak knowledge points and fits the gradual learning process of students. It can be seen that these three algorithms have improved the recommendation effect compared with the CF algorithm, and the improved algorithm in this paper has a better recommendation effect.
Precision, Recall and F1 value of several algorithms
To further investigate the effectiveness of the KSTER algorithm on user satisfaction, two classes were selected for comparison experiments in this paper. Class A adopts the KSTER algorithm to recommend exercises, which means that students improve their achievement with the assistance of the system’s recommended resources. Class B adopts the traditional teaching method, which means that students improve their achievement by doing exercises on their own. Classes A and B in this paper have the same exercise sets. The experimental comparison results of the students’ grades and the number of submissions is shown in Fig. 6 by counting the data from the four exams of the class.

Comparison of student group level analysis.
Figure 6(a) shows the difference between the average score of the class students in the exam and the average score of all classes. Figure 6(b) shows the difference between the average number of submissions of the class students in the exam and the average number of submissions of all classes. As can be seen in Fig. 6(a) and (b), the average score of Class A was higher than Class B. The effect is most evident especially in the second examination. At the same time, the average number of submissions was lower in class A than in class B. This may be due to the improved cognitive level of students in class A with the aid of exercise recommendation and thus less debugging of the program.
Figure 6(c) is the distribution of test scores of class students, and Fig. 6(d) shows the distribution of the number of examination submissions. As seen in Fig. 6(c) and (d), most students in Class A scored between 55 and 85 in the four exams, while Class B had the highest number of students scoring between 40 and 70. Meanwhile, the number of submissions in Class A was concentrated between 16 and 40, while the number of submissions in Class B was concentrated between 24 and 48. This implies that the overall level of students in Class A is higher than that in Class B. The experimental results show that the algorithm proposed in this paper can effectively assist students in programming and improve their learning efficiency.
In order to improve the personalization of online programming system, this paper proposes a personalized programming exercise recommendation algorithm based on knowledge structure tree. The algorithm provides a calculation method for quantifying students’ cognitive level to obtain their knowledge needs. At the same time, a knowledge structure tree is constructed, and a learning objective prediction method is proposed by combining the knowledge needs and the knowledge structure tree to represent and update the learning objective. Furthermore, a matching operator that calculates cognitive level and exercise difficulty is imported based on learning objectives, and exercises are recommended by top-η. The comparison experiments with real-world data demonstrate that the algorithm effectively improves the recommendation accuracy and efficiency. In future work, the semantic relationship of knowledge points and time factor are considered to build more accurate cognitive models of learners, further improve algorithm performance and automate the generation of exercises. In addition, the author will conduct in-depth analysis of programming exercises from the code perspective to dig out user preferences and improve the accuracy of the recommendation algorithm and user satisfaction.
Footnotes
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China (Nos. 61867004, 61762065, and 61762067) and the Graduate Student Innovation Special Fund Program of Nanchang Hangkong University (No. YC2020125).
