Academia.eduAcademia.edu
European Journal of Education Studies ISSN: 2501 - 1111 ISSN-L: 2501 - 1111 Available on-line at: www.oapub.org/edu 10.5281/zenodo.58496 Volume 2│Issue 1│2016 OPTIMIZATION OF EXAM DISTRIBUTION Fadi Safieddine1, Milan Dordevic2, Ahmed M. Hamza3 1,2 American University of M. East, Kuwait University of Portsmouth, United Kingdom 3 Abstract: Academic research findings report high level of cheating in exams involving students copying from each other. Several publications have examined means for preventing cheating by means of exam versions, rotations of questions, and addressing social factors. Yet one preventative aspect of exam cheating seems to be neglected and that is exam distribution. In this paper, the authors introduce the Exam Distribution Problem (EDP). Defining a given k versions of an exam in a classroom with n × m chairs, the paper attempts to find the optimal distribution of exam papers such that every two exams of the same version are at maximal distance from each other. Relevant works in Graph-Theory are examined with simulation of Naïve Algorithm (random) and Sequential Release Algorithm (common) for EDP are reviewed. A cost is assigned for instances where two papers of the same version appear in direct proximity thus associated with higher opportunity for cheating. The results showed that the Sequential Release Algorithm did on average no better than the Random Algorithm. Using Optimization Algorithm, the team presents a new approach, the Dichotomous Interleaved Pairing Algorithm (DIP) that achieves minimal adjacency between two identical exam papers and minimal risk of cheating. Keywords: exam, distribution, EDP, graph-theory, optimization algorithms, cheating Introduction Exam integrity and minimizing cheating during test, quizzes, and other assessments are problems that have been reported in both academic research and media. Many higher educational institutions preferred method is to create several versions of the exam assessment, and distributing these exam papers in a way that minimizes cheating. While the team have accepted this as sufficient, the literature review shows that Copyright © The Author(s). All Rights Reserved Published by Open Access Publishing Group ©2015. 23 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION students cheating in exams have increased and opportunities for cheating remain significantly high. In reviewing established methods in graph-theory and use of datasimulation tool, the team evaluates the risk of cheating as the cost associated with the probability of two adjacent papers of the same version of the exam. Considering three different algorithms, the paper evaluates the outcome of each algorithm. Literature Review Safeguarding exams and reducing possibilities of cheating has and remains a subject of interest in academia [1], [2], [3]. Researchers have employed variety of methods to detect, prevent, and/or reduce the chances of students cheating in the exams [4]. In a survey of 232 undergraduates US students revealed that the most common cheating method is to look at other students exam papers [5]. The same survey showed that as much as 78% of students cheat if the opportunity is presented. In another survey of 536 Iranian students studying at Qom University Medical Science showed that the most common way to cheating is also looking at another students exam paper during an exam [6]. In fact a recent study [4] showed that as much as 50% of students have cheated during an exam. As to the motives, an extensive study of 490 high school and university students in the state of New York [7] indicated that students would attempt to cheat if the opportunity presented itself. In fact, the majority of students indicated that an opportunity to cheat in an exam is considered a justified reason to cheat. “n opportunity to cheat is also presented in another study of an English university [8]. These findings are found to be consistent with an extensive study that reviewed publications over a 10-year period on the subject of cheating [9]. What is more, the authors report that the most dramatic increase in cheating over period between 1963 and 2001 has been exam and test cheating [9]. Many of the academic publications on this subject focused on preventing cheating by creating multiple versions as well as shuffling the questions in a way would make cheating in an exam more difficult [1], [2], [3], [4]. None, however, could be found that looks in details at the exam distribution methodology, especially when dealing with multiple versions of exams in variable sized rooms. This Exam Distribution Problem EDP can be approached by using results obtained from research conducted on a mathematical problem of k-colouring. The classic k-colouring problem is defined as allocation of a colour from 1 to k to each node in a graph such that no two adjacent nodes share the same colour [13]. The k-colouring problem, along with many differences and simplifications, is well studied in both computer science and mathematics [14], [15], [16], [17], [18]. Researchers have conducted a survey of the results associated with the distance colouring of graphs [11]. European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 24 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION In the context the k-colouring of node resembles the EDP, with each node representing a seat in the exam. The aim is to make sure no two versions of the same exam are seated within proximity of each other that would provide an opportunity for students to cheat. A large number of work cited in [12] have suggested an application of the distance colouring of graphs in the frequency assignment problem. The problem of frequency assignment arises when diverse radio transmitters are functioning in a restricted range. Transmitters that are adjacent will affect each other when they have the similar or closely associated frequency channels. In the same context, this could be applied to the EDP to ensure no two adjacent nodes are the same. The problem of assigning frequencies to the different transmitters can then be reduced to a graphcolouring problem [10], [11]. The main result of the research conducted in [10] is the discovery of a disparity between polynomial and NP-hard instances of Distance Colouring Problem. The typical approach observed by the team in exam distributions in the UK and other countries is what the team term Systematic Distribution. In a typical four versions exam of A, B, C, and D, Systematic Distribution of exams works by distributing the exams in these sorted order: “, ”, C, D, “, ”, C, D, “, ”, C, D…etc. The rational suggests that there would not be two identical exam versions next to each other. This also is understood to be a better alternative to Random Distribution. Random Distribution in this context means shuffling the exam versions and distributing them randomly. The probability is that there would be more likely exam versions next to each other. The Systematic Distribution is called Sequential Release Algorithm and Random Distribution is called Naïve Algorithm. Research Questions and Methodology Given that most universities use four versions or less for exams, the team set out to answer the following research questions: 1. How well does a Sequential Release Algorithm of exams score? 2. How well does a Sequential Release Algorithm of exam compare to Naïve Algorithm of exams? 3. Which approach can produce an optimal distribution of exams? To answer these questions, the team will seek to derive what has been suggested as approaches in mathematics on k-colouring in graph-colouring and graph-theory. Then apply these in simulations using Biolayout data simulation application [19]. The simulation will be distributed across a grid of 5x6 with projection on how this approach could be reapplied in other room formations. The team to consider Systematic European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 25 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION Distribution against at least ten random distributions to compare how well the Systematic Distribution would score. Finally the team by means of reflective analysis will propose possible alternatives to the Systematic Distribution that would minimize the risk of cheating. Simulation of Exam Distribution In the context of graph-theory, EDP can be stated as following: In an examination room there are consists of chairs to accommodate that exact number of students. The exam versions of a test paper, comprising a test set , where is the number of exam papers. The objective is to minimize the possibility of having two students sitting next to each other with the same version of the exam thus reducing or eliminating the opportunity of any cheating by selecting the optimal strategy for EDP. The cost function used in k-colouring to indicate proximity of two nodes of the same colour will be used in the context of EDP to indicate risk of cheating. The cost function is calculated according to the rules shown in Figure 1. The weight/cost of all horizontal, vertical and diagonal neighbour edges which connects the same version of exam will be set at cost of one point and the edge will be highlighted red. Moreover, the team considered EDP as a constrained graph theoretical problem. Given a connected weighted graph G = (V, E, W), with a set of nodes V and a set of edges E and W as the distance matrix, i.e. a cost of cheating. 1 1 1 Figure 1: Example of EDP on 4 x 3 grid European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 26 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION Alternatively, simple j-distance in hops can be used as a proximity measure, as in the distance colouring, graph-theoretic formulations. For every non-adjacent node i.e. and , from Figure 1, the weight/cost of cheating is set to be 0.01. This is done because cheating is unlikely when you have an obstacle and considerable distance between these two copies i.e. like inserted between and from Figure 1. Algorithms for EDP We present here the various approaches we will compare for this task. The Naïve Algorithm of exam distribution is carefully analysed in simulations against common Sequential Algorithm method that is typically used in exam paper distributions where versions are involved. Then an alternative algorithm the team termed Dichotomous Interleaved Pairing Algorithm is suggested and compared to the predecessors. Naïve Algorithm We define naïve algorithm distribution as having no bias or structure. A random paper version is picked and assigned to each chair. Alternatively, a random stack of paper versions is prepared and then scattered across all (x, y) chair coordinates. This produces intuitively high chances of neighbouring-version occurrence, although decreasing as the number of versions k grows, see Figure 2. To obtain more accurate results the team have perform ten random runs of naïve algorithm. The outcomes are shown in Table 1. Where the risk of two versions of exams being next to each other at 1 point, the result shows that the cost of ten runs of naïve algorithm is not less than 15 or bigger than 25. The average of ten runs of Naïve Algorithm from Table 1 is 19.8. Number of Simulation Results 1 2 3 4 5 6 7 8 9 10 15 23 21 18 17 19 21 15 25 24 Table 1: Ten runs of Naïve Algorithm European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 27 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION Figure 2: Naive Simulation score 15 Sequential Release (common) Here the versions are arranged in sequential order A,B,C,D, A,B,C,D, and distribute according to the layout of the room, see Figure 3. Starting from the front left side of the room, the versions are distributed vertically in a top-down then down-up method (a snake-like serial distribution . In a class of just students, this approach resulted in at least 20 instances where two versions of the exams are found to be within proximity of each other for an opportunity for cheating. Figure 3: Systematic Simulation score 20 European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 28 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION Dichotomous Interleaved Pairing The interleaved dichotomous-pairing system follows a grid method where, per- row, only two versions are used out of the four. For example, using this algorithm using four versions of an exam (A, B, C, and D), A and B versions will be used as pair and alternate between seats for odd numbered rows while C and D versions will be used as pair and alternate between seats for the even numbered rows. This allows for no neighbouring versions at all, between rows or columns. Algorithm 1 shows the pseudo-code for this method. The simulation of Dichotomous Interleaved Pairing (DIP) Algorithm is shown in Figure 4. Figure 4: Dichotomous Interleaved Pairing 1: S1←{A,B} 2: S2←{C,D} 3: for Row r in rows do i ← column indexes. 4: if r is an odd row then 5: ri ←S1[i mod 2] 6: else 7:ri ←S2[i mod 2] Algorithm 1 Arrange-Exams Interleaved Pairing European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 29 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION Research Analysis Table 2 summarizes the outcomes of three tested Algorithms from Figure 2, 3 and 4. The results from Table 2 show that Dichotomous Interleaved Pairing method significantly outperforms both Sequential Release and Naïve Algorithms on a tested instance. The cost of the Dichotomous Interleaved Pairing on the tested instance is zero, given that this algorithm ensures no adjacent exams. Moreover, this result will always be zero regardless of the composition of a classroom. In other words, for any and in n × m classroom the cost of Dichotomous Interleaved Pairing will be always the same and equal to the lower bound, i.e. 0 (zero). To prove this, the team iterate the distribution starting the from instance tested in the 5 row + 6 column setup (see Figure 4), by reducing or adding any number of rows and columns, the composition/pattern holds, and therefore the cost of cheating will not change. The proof is in the design where the alternations of two versions of an exam will be always a row or column away from the same pair-versions of exams. Those two versions are permuted from versions of the exam. To conclude, by applying Dichotomous Interleaved Pairing on exam distribution problem, where, of cheating in all cases is equal to 0, for any the cost classroom. Thus rendering the suggested algorithm to be optimal against the Sequential Release and Naïve algorithm. Alg/Instance Naïve Algorithm 5x6 Sequential Release 19.8 20 Dichotomous Pairing 0 Table 2: Results of three tested approaches Research Limitation For all experiments the team selected the choice of four exam versions (k = 4), as is typical in most higher education assessments but may not be the standard for all institutions. In addition, the paper did not attempt to model the algorithms of kdistance as a significant number for hop distances greater than one: i.e., the team work with the assumption that it is nearly impossible to cheat with non-adjacent placement of two similar exam versions. The paper considered only adjacent nodes as prone for cheating, which maybe disputed. To maintain simplicity of results, the simulation experiments conducted were limited to the Naïve and Sequential Release algorithms by typical room size although the paper has been able to project it results on other instances. The team also did not extensively model exam room setups that are more esoteric such as having only two European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 30 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION rows of chairs or indeed one row. The conditions used, the team believes, represent enough preliminary results to show the practical applicability of this research to most exam room scenarios with minimal additional overhead to examiners such as preparing a larger number of versions or requesting larger rooms. Conclusion and Further Research In this paper, the team has been able to identify flows in what is considered the most common method of exam distribution. The team introduced a problem not well reported in academic publications as EDP. The team suggests an approach that would minimize risk of cheating and minimize adjacency between two similar versions. And while the method suggested (DIP) has been proven to be applicable in any room size, further research is needed to consider instances where the number of versions can be optimized below four versions demonstrated in this case study. Also further research could look at large rooms where distances could be considered as sufficient obstacle as opposed to having a person or a seat between versions to be the sufficient obstacle. With increasing use of technology for exams researchers can consider how creating infinity number of versions may compare to the results that the DIP algorithm suggested in this paper. References [1] Davis, S. F., Grover, C. A., Becker, A. H., & McGregor, L. N. (1992) "Academic Dishonesty: Prevalence, Determinants, Techniques and Punishments." Teaching of Psychology, 19, 16-20. [2] Dick, M., Sheard, J., Bareiss, C., Carter, J., Joyce, D., Harding, T., and Laxer, C. (2003) Addressing student cheating: definitions and solutions. ACM SIGCSE Bulletin, 35 (2). pp. 172-184. ISSN 0097-8418. [3] Lathrop, A., & Foss, K. (2005). Guiding students from cheating and plagiarism to honesty and integrity: strategies for change. Westport, CT: Libraries Unlimited. [4] Richard J. Fendler & Jonathan M. Godbey (2016) Cheaters Should Never Win: Eliminating the Benefits of Cheating. Journal of Academic Ethics 14 (1):71-85. [5] M, Moffat. (1990) Undergraduate Cheating, ERIC document ED334921. [6] Akram Abedinipoor , Fatemeh Samadi , Somayeh Momeniyan (2014) Prevalence and factors associated with cheating among students of Qom University of Medical Sciences. Journal of Medical Education Development. J Med Edu Dev 2015, 8(19): 73-80. European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 31 Fadi Safieddine, Milan Dordevic, Ahmed M. Hamza OPTIMIZATION OF EXAM DISTRIBUTION [7] Jensen, L. “., “rnett, J. J., Feldman, S. S., and Cauffman, E. . It s wrong, but everybody does it: Academic dishonesty among high school and college students. Contemp. Educ. Psychol. 27: 209–228. [8] Newstead, S.E.,Franklyn-Stokes, A. and Armstead, P. (1996), 'Individual differences in student cheating', Journal of Educational Psychology, 88, 229–41 [9] Donald L. McCabe, Linda Klebe Treviño, Kenneth D. ”utterfield, in “cademic Institutions: “ Decade of Research, Ethics & ”ehavior Cheating : 9–232 [10] Sharp, A. (2007). Distance colouring, In Algorithms–ESA 2007, Springer Berlin Heidelberg, pp. 510-521. [11] Kramer, F., & Kramer, H. (2008), A survey on the distance-colouring of graphs, Discrete mathematics, 308(2): 422-426. [12] M. Molloy, M.R. Salavatipour, Frequency channel assignment on planar networks, in: Proceedings of ESA 2002, Lecture Notes in Computer Science, Vol. 2461, Springer, Berlin, 736–747. [13] Garey, M. R., & Johnson, D. S. (1979), A Guide to the Theory of NP-Completeness, WH Freemann, New York. [14] Bondy, J., Murty, U.: Graph Theory with Applications. The MacMillan Press Ltd (1978) [15] Fiorini, S., Wilson, R.J.: Edge-colourings of graphs. In Beineke, L.W., Wilson, R.J., eds.: Selected Topics in Graph Theory. Academic Press, Inc., London (1978) 103–126 [16] Bollob´as, B., Harris, A.J.: List-colourings of graphs. Graphs and Combinatorics 1 (1985) 115–127 [17] Wilson, B.: Line-distinguishing and harmonious colourings. In Nelson, R., Wilson, R.J., eds.: Graph Colourings. Pitman Research Notes in Mathematics Series. Longman Scientific & Technical, Longman house, Burnt Mill, Harlow, Essex, UK (1990) 115–133 [18] Chetwynd, A.: Total colourings of graphs. In Nelson, R., Wilson, R.J., eds.: Graph Colourings. Pitman Research Notes in Mathematics Series. Longman Scientific & Technical, Longman house, Burnt Mill, Harlow, Essex, UK (1990) 65–77 [19] Wright, D. W., Angus, T., Enright, A. J., van Dongen, S., & Freeman, T. C. (2014). BioLayout Express 3D Version 3.2. Creative Commons licensing terms Author(s) will retain the copyright of their published articles agreeing that a Creative Commons Attribution 4.0 International License (CC BY 4.0) terms will be applied to their work. Under the terms of this license, no permission is required from the author(s) or publisher for members of the community to copy, distribute, transmit or adapt the article content, providing a proper, prominent and unambiguous attribution to the authors in a manner that makes clear that the materials are being reused under permission of a Creative Commons License. Views, opinions and conclusions expressed in this research article are views, opinions and conclusions of the author(s). Open Access Publishing Group and European Journal of Education Studies shall not be responsible or answerable for any loss, damage or liability caused in relation to/arising out of conflicts of interest, copyright violations and inappropriate or inaccurate use of any kind content related or integrated into the research work. All the published works are meeting the Open Access Publishing requirements and can be freely accessed, shared, modified, distributed and used in educational, commercial and non-commercial purposes under a Creative Commons Attribution 4.0 International License (CC BY 4.0). European Journal of Education Studies - Volume 2 │ Issue 1 │ 2016 32