YAP3: improved detection of similarities in computer program and other texts

ABSTRACT

In spite of years of effort, plagiarism in student assignment submissions still causes considerable difficulties for course designers; if students' work is not their own, how can anyone be certain they have learnt anything? YAP is a system for detecting suspected plagiarism in computer programs and other texts submitted by students. The paper reviews YAP3, the third version of YAP, focusing on its novel underlying algorithm - Running-Karp-Rabin Greedy-String-Tiling (or RKS-GST), whose development arose from the observation with YAP and other systems that students shuffle independent code segments. YAP3 is able to detect transposed subsequences, and is less perturbed by spurious additional statements. The paper concludes with a discussion of recent extension of YAP to English texts, further illustrating the flexibility of the YAP approach.

REFERENCES

• 1: J. A. W. Faidhi , S. K. Robinson, An empirical approach for detecting program similarity and plagiarism within a university programming environment, Computers & Education, v.11 n.1, p.11-19, Jan. 1987 [doi>10.1016/0360-1315(87)90042-X]
• 2: G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 3: Sam Grier, A tool that detects plagiarism in Pascal programs, Proceedings of the twelfth SIGCSE technical symposium on Computer science education, p.15-20, February 26-27, 1981, St. Louis, Missouri, United States
• 4: Paul Heckel, A technique for isolating differences between files, Communications of the ACM, v.21 n.4, p.264-268, April 1978 [doi>10.1145/359460.359467]
• 5: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 6: KRUSKAL, JOSEPH B., "An Overview of Sequence Comparison", Time Warps, String Edits and Macromolecules: The'Theory and Practice of Sequence Comparison, ed. David Sankoff and Joseph B. Kruskal, pp. 1--44, Addison Wesley (I983) (Chapter 1).
• 7: VERCO, KRISTINA L. AND MICHAEL J. WISE, "A Comparison of Structure-Metric and Counting Metric Plagiarism Detection Systems", Twenty-Seventh SIGCSE Technical Symposium, Philadelphia, U.S.A. (February 15-17, 1996) (Submitted to conference).
• 8: G. Whale, Identification of program similarity in large populations, The Computer Journal, v.33 n.2, p.140-146, April 1990 [doi>10.1093/comjnl/33.2.140]
• 9: M. J. Wise, Detection of similarities in student programs: YAP'ing may be preferable to plague'ing, Proceedings of the twenty-third SIGCSE technical symposium on Computer science education, p.268-271, March 05-06, 1992, Kansas City, Missouri, United States
• 10: WISE, MICHAEL J, "Running Karp-Rabin Matching and Greedy String Tiling", Basser Department of Computer Science Technical Report, Sydney University(1994)(ftp://ftp.cs.su. oz.au/michaelw/rkr_gst.ps Revises Basset Technical Report 463, March 1993).
• 11: WISE, MICHAEL J, "Neweye~'. A System for Comparing Biological Sequences Using the Running Karp-Rabin Greedy String-Tiling Algorithm", Third hzternational Conference on Intelligent Systems for Molecular Biology, ambridge,England., pp. 393-401 (July 16-19, 1995).

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Theory