PPIG 2012 - 24th Annual Workshop
Schema Detection and Beacon-Based Classiffcation for Algorithm Recognition
Ahmad Taherkhani
Abstract: 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 speciffc 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-speciffc beacons from the detected code and uses them as the learning data to construct a classiffcation 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 classiffcation measured by leave-one-out cross-validation technique is 97.3%.