# An algorithm for automatic checking of exercises in a dynamic geometry system-iGeom.pdf

equivalent if, and onlyif, they have the same output when the same input is applied. Ifthe student’s solution is equivalent tothe template’s solution, then we consider the student’s solution as a correct solution. Our software utility provides both1980s, with the emergence of ‘‘personal computers” (PCs), that the use of this machine and its resources (e.g.,*Corresponding author. Tel.: +81 6 6879 8416; fax: +81 6 6879 2123.E-mail addresses: isotani@acm.org (S. Isotani), leo@ime.usp.br (L. O. Branda˜o).1To learn more about the history of the computer, visit the timeline of computing history at http://www.hofstra.edu/ComputingHistory.Available online at www.sciencedirect.comComputers Automatically checking exercises; Distance education; Geometry; iGeom1. IntroductionThe computer has been used in education since its earliest appearance in 1945.1However, it was only in theSeiji Isotania,*, Leoˆnidas de Oliveira Branda˜obaThe Institute of Scientific and Industrial Research, Department of Knowledge Systems, Osaka University,8-1 Mihogaoka, Ibaraki, Osaka 567-0047, JapanbThe Institute of Mathematics and Statistics, University of Sa˜o Paulo, Rua do Mata˜o, 1010, Cidade Universita´ria,Sa˜o Paulo, SP, 05508-090, BrazilReceived 25 October 2007; received in revised form 6 December 2007; accepted 23 December 2007AbstractOneofthekeyissuesine-learningenvironmentsisthepossibilityofcreatingandevaluatingexercises.However,thelackoftools supporting the authoring and automatic checking of exercises for specifics topics (e.g., geometry) drastically reducesadvantagesintheuseofe-learningenvironmentsonalargerscale,asusuallyhappensinBrazil.Thispaperdescribesanalgo-rithm,andatoolbasedonit,designedfortheauthoringandautomaticcheckingofgeometryexercises.Thealgorithmdynam-icallycomparesthedistancesbetweenthegeometricobjectsofthestudent’ssolutionandthetemplate’ssolution,providedbytheauthoroftheexercise.Eachsolutionisageometricconstructionwhichisconsideredafunctionreceivinggeometricobjects(input)andreturningothergeometricobjects(output).Thus,foragivenproblem,ifweknowonefunction(construction)thatsolves the problem, we can compare it to any other function to check whether they are equivalent or not. Two functions areAn algorithm for automatic checking of exercisesin a dynamic geometry system: iGeomdoi:10.1016/j.compedu.2007.12.004software) significantly impacted teaching and learning processes (Oldknow, 1997). Today, in Brazil and other1284 S. Isotani, L. O. Branda˜o/Computers Litto,2006). In this context, these online environments that support teaching and learning processes have becomevirtual classrooms, where students and teachers can communicate and interact using tools, including chatrooms, forums, emails, wikis, virtual blackboards, etc.The use of the Internet and computers can bring great benefits to the teaching of mathematics, but in orderto achieve such goals, it is necessary to choose and create appropriate programs and methodologies that takeadvantage of the computer’s positive characteristics. Good examples of this include dynamic geometry (DG)programs, which can benefit teaching and learning processes (Ruthven, Hennessy, SantosRuthven et al., in press; Sinclair, 2005). In spite of the great benefits for teaching and learning, as well as theexistence of useful DG programs, including GSP (Jackiw, 1995), Cabri (2007), Cinderella (Kortenkamp,1999), C.a.R. (Grothman, 1999), and Tabulae (Moraes, Santoro, and (b) develop tools allowing for com-munication between DG programs and learning management systems (LMS) that facilitate distribution, man-agement, adaptation, and reception of exercises or any other content.Today, two DG programs possess tools for authoring and checking exercises, including Cinderella (Kor-tenkamp, 1999) and C.a.R. (Grothman, 1999). The contributions of these programs inspire many teachersto include DG programs in classroom activities. However, in the current versions of these programs, thereare some limitations for their use on distance education courses over the Internet. For instance, it is not pos-2Blended learning is broadly used to define a course that combines usual classroom activities and online activities.sible to satisfactorily link these programs to LMS, allowing for eﬀective management and/or adaptation of thecreated content. This means that these programs cannot personalize their content in real time nor considerS. Isotani, L. O. Branda˜o/Computers Gallier, 2003; Gilmore, 1970). The developed algorithmof this paper is not as formal as a proof, but does enable the instantaneous checking of a geometric exerciseby comparing it with a solution’s template. The main benefits of this approach include a program that is (a)fast enough to be used over the Internet to support the use of DG programs in distance education courses;(b) able to check any kind of geometric construction and return whether the construction has the necessaryproperties to solve an exercise; and (c) able to run on computers with low-processing capabilities, which isvery important in Brazil, where many computers used in public schools are out-of-date. Furthermore, wewill present results using this algorithm, implemented on iGeom, together with an under development learn-ing management system, referred to as SAW (Moura, Branda˜o, the modifica-tion of characteristics of the objects (e.g., color, size); options for saving or recovering constructions in diﬀer-ent formats; and other advanced resources. Besides these, iGeom has special resources for creating scripts(functions used to create automatic geometric constructions) and fractals. Fig. 1 depicts the interface of theiGeom, including fractals created using a recursive script.The iGeom has been developed considering the computational restrictions of computers in Brazil. This phi-losophy makes iGeom run eﬃciently in both residential and personal computers that have low-processingcapabilities (e.g., computers using a microprocessor similar to Intel i386). Furthermore, it can be used withoutrestrictions with any other learning management system (Branda˜o, Isotani, Moura et al., 2007). The iGeom program has been used together with SAW in diﬀerent courses. One of theseincludes a course directed towards public school teachers and people interested in teaching mathematics usingcomputers. Another use includes an obligatory discipline oﬀered for a degree course in mathematics, titled‘‘Notions of teaching of mathematics using computers”. Each year, more than a hundred students and teachersare enrolled in these courses. The use of iGeom + SAW, including some of the obtained results using the auto-matic checking tool on the Internet, will be shown in detail in Sections 4 and 5.2. Authoring and automatically evaluating exercisesThe action of evaluating or checking exercises is a complicated process (Chou et al., 2000; Gelernter,1963; Kortenkamp, 1999). Because of this, automation is not a trivial matter. It requires the applicationFig. 1. The interface of the iGeom showing fractals created using recursive script.Table 1Comparison between the resources of some DGSProgram Portability ADDs Script Rec Web Com AA LicenseiGeom X X X X X X X FreeCabri X X CommercialC.a.R X X X X GNUCinderella X X X X CommercialGSP X X X CommercialTabulae X X X X CommercialS. Isotani, L. O. Branda˜o/Computers Chou et al., 2000). At present, several methods exist for accomplishing an automatic proof ingeometry. Some of them are (Gao Gallier, 2003). For online courses, the time available for response is extremely limited. Feedbackshould be given almost instantaneously (real time). Additionally, in Brazilian public schools, most computershave low-processing capabilities, which demand programs and algorithms that do not consume a great deal ofcomputer processing time.Instead of attempting to prove a student’s construction/solution, a numerical evaluation compares the stu-dent’s answer-objects with the corresponding teacher’s answers-objects. This comparison is made using a dis-tance criterion between the objects. For instance, if the problem is to determine the middle point betweenpoints A and B, the distance is verified between the point of the student’s construction and the point of theteacher’s construction according to an established criterion. Programs that use a similar method include Cin-derella (Kortenkamp, 1999), C.a.R. (Grothman, 1999), and iGeom (Isotani (b) the selection of initial objects (including the selection of a statement); (c) the selection of answer-objects; (d) the use of the unable/enable buttons; and (e) saving the exercise or exporting it into HTMLformat.The construction of the solution template is accomplished the same as any other construction. For exam-ple, to construct the median line of two points, one possible construction requires the authors (a) to createpoints A and B; (b) to create a segment s0 that connects A and B; (c) to create a middle point M between Aand B; and (d) to create the line r (median) perpendicular to the segment s0, which passes through M,shown in Fig. 3.When construction is complete, the author can initiate an authoring window (to the right of Fig. 3) andselect the initial objects (those that will appear at the beginning of the exercise) using the ‘‘marcador” button(in Fig. 3, the icon with a red square around it). The selection of the answer-object is completed in a similarfashion.In the authoring window, it is possible to see which objects have been selected, as well as remove or addother objects. To disable/enable buttons in the student main interface, one can click on the buttons shownat the bottom of the authoring window. Thus, teachers can select tools that will be available to learners duringthe resolution of the exercise. For example, the buttons ‘‘middle point”,‘‘perpendicular” and ‘‘parallel” can bedisabled and, thus, students will be unable to use these tools to solve the given problem. Finally, authors cansave the exercise in a stand-alone version of iGeom, or save it as an HTML file.Along with the authoring tool, a resource for automatically checking a student’s solution has been devel-oped. When a student opens an exercise in iGeom, similar to the example shown in Fig. 3, he or she will onlysee points A and B and the message, ‘‘Given two points A and B, build the median line”. Furthermore, the but-tons disabled by the teacher during the authoring phase will not appear in the menu. Thus, the student will beunable to use them.After a student completes a given exercise, he or she needs to select the answer-object that he or she believesto be the correct answer (e.g., select the median line for his or her construction). Then, the evaluation algo-rithm begins. If the student’s solution is evaluated as incorrect, the iGeom finds a counter-example or a con-figuration (instance) of the construction where the selected answer-objects do not satisfy the desired properties(more details on how to find the counter-example is shown in Section 3). The use of counter-examples aidsboth teachers verifying a student’s construction and students who need to visualize their mistakes. AnotherS. Isotani, L. O. Branda˜o/Computers ogp2;.;ogpiðÞand oga1;oga2;.;ogaiC0C1, respectively, then the distance between OGpe OGa, can be expressedas shown in Table 2.A solution (geometric construction) can be represented as a function that receives a list of geometric objects(input) and returns another list of geometric objects (output):S : OGi!OGfð6ÞAn instance of construction S is the application of S over a given configuration of objects. Once the dis-% is used to obtain the rest of the division (function module).need of the minimum (min), when objects are from the family of segments, is based on the desire tonot only the distance between segments AB and CD, but also their permutations AB and DC,CD, BA and DC, without diﬀerentiation between them. In other words, for segments, the distanceon does not distinguish segment AB from segment BA.the distance among geometric objects is defined, we can define the distance between pairs of geometriccircumference can be represented by (x, y, r), where (x, y) are the coordinates of its center and r is its radius;and a segment s =[(x1, y1), (x2, y2)] can be represented by (x1, y1, x2, y2). Thus, if we consider just the fam-ilies of points, circumferences and segments, given two objects of a same family, og1eog2, if ‘11;‘12;.;‘1iC0C1and ‘21;‘22;.;‘2iC0C1, represent og1eog2, respectively, then we can define the function dist according to theEq. (2).distðog1;og2Þ¼j‘11C0‘21jþj‘12C0‘22j; ðog1;og2Þ2FpXFpj‘11C0‘21jþj‘12C0‘22jþj‘13C0‘23j; ðog1;og2Þ2FcXFcminP4i¼1j‘1iC0‘2ij;P4i¼1j‘1iC0‘2ðiþ1Þ%4þ1j8:9=;; ðog1;og2Þ2FsXFs8:ð2Þoginstance, a point can be represented by (x, y), where x and y are the coordinates of a point; a3.1. Numerical evaluationThe result of the evaluation is a measurement of the distance between the student’s solution and the tea-cher’s solution (a correct solution given for a problem). To complete this evaluation, it is necessary to definethe distance criterion among the geometric objects. We have defined the distance criterion only for pairs ofobjects of the same family or type. To simplify, we only name examples from the more common families ina construction, including the family of points (Fp), the family of circumferences (Fc) and the family of seg-ments (Fs). The sets of all families of objects will be represented by Fog.By doing so, the distance criterion is the function dist that receives a pair of geometric objects (og1,og2)2FogXFogand returns a value of Rþ:dist :ðog1;og2Þ!Rþð1ÞThe computational description of the objects is defined for each family of F as a list of numerical val-ple, this solution allows for false positives (a wrong exercise evaluated as correct) or false negatives1292 S. Isotani, L. O. Branda˜o/Computers OGaÞ¼þ1 ð3ÞIf #OGp=#OGa= n,then Ip=(p1, .,pn) and Ia=(a1, .,an) two permutations on the first natural n,distðIp;IaÞ¼Pni¼1dist ogppi;ogaaiC16C17; if htipo ogppiC16C17¼tipo ogaaiC0C1;i2f1;.;ngiþ1; c:c:8:ð4Þtipo(og) being a function that returns the type of geometric object og.Then,if Pnis the set of all of the permutations of first natural n:dist OGp;OGaC0C1¼min dist Ip;IaC0C1;8 Ip;IaC0C12PnXPnC8C9ð5ÞIn other words, among all of the permutations of objects of OGpe OGa, dist OGp;OGaC0C1is the sum of the distances among each pair ofobjects of same type that results in the smallest value.Table 3(a correct exercise evaluated as incorrect), but as we show in session 4, in practice, it works well. It is also pos-sible to increase the number of instances tested or implement other modifications of parameters that wouldreduce or eliminate wrong evaluations.3.2. The evaluation algorithmFrom now on, when it is implicit or indiﬀerent as to which list of geometric objects should be used, thesimplified notation S will be used.Based on the numerical evaluation presented in the previous section, we have created an algorithm com-posed of four main steps. Th