Schema Detection and Beacon-Based Classification for Algorithm Recognition

Ahmad Taherkhani

We introduce a method for recognizing algorithms based on programming schemas, which are generic conceptual knowledge with details abstracted out, and beacons, which are key statements that suggest existence of specific structures in code. First, the method detects the schemas related to the implementation of the target algorithm and next it computes the characteristics and algorithm-specific beacons from the detected code and uses them as the learning data to construct a classification tree for recognizing new unseen instances.

We demonstrate the method and its performance for searching, heap, basic tree traversal and graph algorithms implemented in Java (N = 222). The results show that 94.1% of the schemas are detected correctly and the estimated accuracy of the classification measured by leave-one-out cross-validation technique is 97.3%.

Type of Publication: Paper
Conference: PPIG 2012 - 24th Annual Workshop
Publication Year: 2012
Paper #: 2
TitleSchema Detection and Beacon-Based Classification for Algorithm Recognition
Publication TypePaper
AuthorsTaherkhani, A
PPIG Workshop: 
2012-11-24th