ALGORITHM RECOGNITION FOR PROGRAMMING TUTORING BASED ON FLOW GRAPH PARSING

摘要

Plan-recognition with template matching shows reasonable performance for recognizing general control structures. However, problems containing well-defined algorithms such as sorting and searching are difficult to recognize by the template-based methodology alone, because an algorithm is often highly optimized and therefore hard to divide into smaller meaningful units. Based on this observation, we propose an algorithm recognition methodology to augment the plan-recognition approach. Our algorithm recognition approach is based on the flow graph parsing which performs a partial recognition of programs. The methodology is extended to completely understand algorithm implementations by providing the information of the program's goal, a specification of programming assignment in tutoring environment. Utilization of goal information is two-fold; extending the role of transformation rules to represent algorithm-specific information and looking for salient graph parts of algorithm plan to determine which has been used to implement the goal. Preliminary evaluation was performed on students' programs containing sort algorithm. [References: 28]