Programming Style – Part of Grading Scheme in Informatics Olympiads: Lithuanian Experience
Institute of
Mathematics and Informatics, Akademijos 4,
2600 Vilnius, Lithuania
Jurate@ktl.mii.lt
Abstract. In International Olympiads in Informatics (IOI) contestants express their algorithms in programs which are graded using black-box method. This method is criticized for it does not reveal the essential features of the algorithm implemented. One of important features of a good program not revealed by automated testing is programming style. In Lithuanian Informatics Olympiads, up to 10% of points the contestants can score for program clarity and elegancy. The paper investigates the impact of such evaluation to the scientific quality of the Olympiads.
Keywords: programming style, informatics olympiads, Lithuanian experience, program correctness
1 Introduction
International Olympiad in Informatics (IOI) is yearly international competition in the discipline of computer science, the tasks are of algorithmic nature. Individual contestants from all over the world take part in it [4]. The contestants have to solve six tasks in two contest days. The algorithms have to be designed in one of the allowed programming languages (Pascal, C, C++). Many national and regional competitions are organized under IOI model, among them Lithuanian Olympiads in Informatics.
Grading in IOI is based solely on automated testing and the programs have to run indefectible in order to get a good score. The aim of grading is to reveal the algorithms implemented, to evaluate their suitability to solve the particular task correctness, efficiency, elegancy, implementation and to assign marks according to the mentioned criteria. The current IOI grading approach receives a lot of criticism because execution-only grading method does not reveal the essential features of the algorithm implemented by the contestant. Therefore even the scientific value of the contest can be doubted [11]. Programming style is also not graded in IOI which unjustifiably equalizes messy and unreadable programs with elegant and clear ones. In Lithuanian Olympiads in Informatics the grading procedure is slightly different. The contestants have to submit verbal description of their algorithm together with a working program. The elegance and clarity is also graded.
Several questions might be raised related to the programming style of programs submitted during the contest: should it be included into the grading schema or not, if it is included – should it be just an advantage (if the program is clear and elegant, then it will get some extra points) or a necessity (if the program is messy and unreadable it does not get any points at all), is there an impact of grading programming style to the scientific quality of the Olympiads.
2 Grading Programming Style in Lithuanian Olympiads
In Lithuanian Olympiads of Informatics (LOI) tasks are of algorithmic nature as in IOI. In many tasks in Lithuanian Olympiads programming style is evaluated. In that case 90% of points are given for testing results and verbal description of an algorithm, the remaining 10% points – for program elegance, structure and simplicity. Those 10% of points can only be awarded if the program scores ³50% of points for automated testing in order to avoid giving points for programs that even do not try to solve the task.
“A programming style is understood as an individual’s interpretation of a set of rules and their application to the writing of source code in order to achieve the aim” [8] that the source code is readable and understandable. It can be said that by the concept programming style it is understood everything that is related to program clarity, simplicity and generality. There was developed taxonomy for programming style [9], however still it difficult to define the elements of programming style precisely (the contestants do want the precision when it deals with getting or loosing points) and to express the conformance to them quantitatively [3].
There are developed some formal criteria in Lithuanian Olympiads in Informatics, which make guidelines for the evaluators. The criteria are also the guidelines for the competitors.
One of the main requirements is consistency everywhere in the program: in text formatting, naming, in processing data, in control structures, etc. Importance of consistency was much stressed in [7].
The other basic requirements are: neat and clear text formatting, text indentation revealing program structure, spaces used to give more clarity and suggest grouping, appropriate use of comments, descriptive names, reasonably selected and used data structures, structural program (separate groups of computational steps are separated into procedures or functions). These requirements were based not only on general requirements for programming style, but also on the most common offences to programming style the competitors make in Informatics Olympiads.
3 Should Programming Style be Included into Grading Scheme?
There are continuous discussions about the existing grading scheme in Informatics Olympiads, in particular in IOI. The question of whether the programming style should be included into the Informatics Olympiads grading schema should also be raised. The positive part of marking programming style is obvious: program simplicity and clarity and elegance (which are essential feature of good programs at all levels of computing) will be taken into account and two equally correct and efficient programs but with different quality of programming style will not be equalized. Therefore the grading will be fairer.
Needless to say there are many other reasons why there might occur a need to analyze program source by others than the author of the program (the most obvious one - analyzing technical appeals) during the contest. It is known that the programming style has much influence on its comprehensibility [8][9].
One of the reasons in Informatics Olympiads why the algorithm is not analyzed by the evaluators is time constraints: it would take too much time to decide which algorithm is implemented, is it correct and how good it is implemented by simply analyzing program source, especially if programming style is far from perfect. However this is not true about the programming style: it does not take too much time to decide whether the program is written in understandable manner or not.
The other concern, valid for international events is verbosity (contestants naming and writing comments in native languages). On the one hand there are many aspects of programming style that are language independent and can be graded. On the other hand the team leaders can help with translation of comments. There is a fear that the results can be influenced by the English skills of the team leaders. However this should not be a big concern, because their English skills are obligatory for the team leaders – English is an official IOI language and the team leaders have always been responsible for translating task formulations to their native languages.
There are two other concerns about inclusion programming style into grading scheme which will be discussed in more detail. One them is the reappearing of subjectivity factor in Informatics Olympiads, another one – relating grading of programming style to program (or algorithm) correctness.
3.1 The Subjectivity Factor in Grading Programming Style
It is bad if the competitors underestimate the importance of program clarity and treat the criteria as merely a collection of language specific rules [9].
One of the negative features of grading programming style is that it brings back subjectivity factor to the Olympiad, for it is obvious that the same program might look clearer to one evaluator than to the other despite the existence of formal criteria for evaluating programming style. And of course any personal decision in grading will be a cause to appeal (in the last years there were almost no appeals in IOI’s ). However, “the desire for automation as carried out in the past has blinded the IOI community: the real work of the work of the competitors remained invisible” [11]. Subjectivity factor should not be feared, for subjective decisions may lead to more objective scoring that “objective” automated grading. Besides, in other science Olympiads, for example in International Mathematics Olympiads (IMO) grading is not automated [10] and therefore includes subjective decisions, however these contests are not considered in-objective just because the absence of automated grading.
In Lithuanian Olympiads in Informatics programming style was part of grading schema for many years, the contestants could be awarded up to 10 of points (out of 100) for it. Despite the existence of formal criteria for evaluation, the practice shows that different evaluators might treat the same program differently. Usually this difference is 1-2 points and only in very few worst cases 4-5 points (but in that case the average is taken and thus subjectivity is decreased).
The answer to the subjectivity problem can be obtained by answering the following question: whether it is more in-objective to treat programs with bad and good programming style as of equal quality (if their performance is the same) or to make distinction between them however with 1-2 point error possibility.
3.2 How to Relate Grading of Programming Style to Program Correctness
Another important issue is how to relate grading of programming style to “program correctness”. Program correctness was taken into commas, because black-grading does not fully check program correctness [11]. However it is obvious, that certain relationship should be invented.
For example, a three line program which prints random number (therefore is neat, clear and simple) and does not solve the task at all should not be awarded points for program clarity[1]. In LOI there is an accepted rule, that programming style is evaluated only if the program scores more than 50% of points for tests. This is not fully objective because the black-box grading itself is not objective enough. There are cases where a minor mistake results in low score [1] and it would not be fair to loose 10% more points.
There might be another approach to look at all the programs submitted by the contestants and to evaluate all those that try to solve the task. If the program does not try to solve the task (e.g. outputs random numbers or just solves the sample tests) it can be identified easily by the evaluator by just looking at the text of a program. If the program does not try to solve the task but is obfuscated on purpose (even such cases were observed by [11]) or so messy, that it is impossible to determine whether it tries to solve or not, then – would the clarity and understandability of such a program be worth any points at all (even if we ignore whether it tries to solve the task or not).
There might arise discussions on whether it is worth giving points for a program which fails (even though tries) to solve the task. Here I would like to quote one IOI contestant “Once the program in the Olympiad is being designed in clear and structured way from the very beginning, it does not fail”[2]. It was a brave statement; however there is much truth in it, especially when we are talking about the type of programs designed during informatics Olympiads. This implies that once the program designed during the Olympiad, fails (not counting minor mistakes), then in many cases there are also problems with quality of programming style[3]. Analysis of programming style grading results in the next chapter supports this idea.
The ability to write nice and elegant programs is already a skill and a very important skill which is not usually the focus of computer science and programming courses [5].
“Olympiads in informatics is an attractive form of learning and a very important motive to programming skills for their participants” [2] and this form of learning should be used to improve the quality of programming style of the contestants.
Therefore it should be encouraged in IOI and other Informatics Olympiads among the most talented young people in the field of computer science.
4 Statistics of Results of Grading Programming Style in One LOI’2006 Task
G. Grigas in [3] investigated relationship between programming style and program correctness. He analyzed programming style of nearly 700 hundred programs made by competitors from various countries and calculated correlation coefficients between program correctness and programming style in various ways. However the dependencies that were received were not strong.
The task, Acorns[4], given in the final round in Lithuanian Olympiad in Informatics in 2006 was chosen to collect statistics. There were submitted 130 solutions to this task and 34 of them were identified as not solving the task at all or as being in the initial phase of development where no output is produced at all. Those programs were not counted. The programming style of all the remaining 96 programs was graded. The figure 1 shows relationship between points received for programming style and points, received for black box-testing.
Fig. 1. Chart showing relation of testing results (y axis) with programming style grading results. The correlation between these two values is 0.33.
It might be stated that the results obtained here are similar to those obtained by G. Grigas.
The statistics shows that the programming style of nearly half of the contestants is lower than satisfactory (i.e. below 5 points). There was compared programming style of different programs designed by the same contestants in the final round in LOI’2005. There was no essential difference between the programs where the programming style was graded and where not (the contestants knew the grading procedure in advance). The only visible difference was in the amount of comments – there were no or significantly less comments in the programs where the programming style was not graded. This can lead to the conclusion that in contest environment the students concentrate on the task apply the programming style they follow in everyday life and only add some extra comments to improve it.
The results of black box testing reveal (or are expected to) combination of two different things: 1) suitability of algorithm to solve particular task; 2) correctness of algorithm implementation. The correlation above shows relation of programming style with those two things. In order to get more exact results we tried to separate those two features in the solutions and to count the correlation between programming style and correctness of implementation of algorithms. The suitability of algorithm to solve particular task does not seem to have direct relation to programming style.
Therefore the implementations of algorithms of task Acorn were also graded. In LOI it is required to submit verbal description of algorithms together with the program, therefore in most cases it is possible to determine what kind of algorithm was implemented (or intended to implement) in the program. Under this grading the program got full marks if it implemented the algorithm correctly irrespective of whether the algorithm itself is correct and effective or not. Figure 2. shows the relation between correctness of implementation and programming style.
Fig. 2. Chart showing relation of correctness of implementation (y axis in 5 point scale) with programming style grading results. The correlation between these two values is 0.468.
The second figure shows much stronger tendency that the better programming style, the better contestant succeeds to implement his algorithm (not necessary correct or efficient one).
5 Program Clarity in the Olympiads – Advantage or Necessity?
There is one good observation made by B. W, Kernigan and R. Pike about the style of programs:
“In a world of … relentless pressure for more of everything, one can loose sight of the basic principles – simplicity, clarity, generality – that form the bedrock of good software” [5].
This should not happen to the Olympiads. National or International Olympiads in Informatics is the place where the top high school students from the world (or a particular country) come to compete. The lesson they might take from there is that an algorithm implemented in “quick and dirty” style and giving satisfactory output is as good as clear and elegant program. This lesson they might take further to their lives where they many of them will pursue career in the field of Informatics.
Personal teaching experience shows that it is quite easy to teach the students who had no prior programming experience to adopt good programming style and it is unbelievably difficult to make the students to accept good programming style after they have been writing programs with bad style for few years. The general attitude towards programming style issue in such a high level contests is very important.
Therefore the approach to force good programming style as a necessity – to reject submissions (programs) that do not meet even the minimal requirements for program clarity – should be considered.
6 Conclusions
Programming style is an important feature of a good program. The statistical analysis showed that there is a strong correlation between correctness of program implementation and programming style in Informatics Olympiads. In Informatics Olympiads programs with different quality of programming style should not be treated equally. There are concerns about inclusion of programming style to grading scheme in Informatics Olympiads, in particular the reappearing factor of subjectivity and ensuring that programs that do not attempt to solve the task do not get points for programming style as well. In IOI or other international competitions the factor of multilinguality should be taken into account. Programming style has been a part of grading schema in Lithuanian Olympiads, the practice was successful, improved the scientific quality of the Olympiads and had positive indirect educational effect to the quality of programming style of the contestants. It is highly important that the Olympiad in Informatics would not confirm the wrong belief of some contestants that “quick and dirty” written program once it gives satisfactory results is as good as elegant and simple one. Therefore the approach to force good programming style as a necessity – to reject programs that do not meet the minimal requirements – in the top level competitions should be considered.
References
1. Foriðek, M.: On suitability of programming competition tasks for automated testing. International Workshop. In: Perspectives on Computer Science Competitions for (High School) Students. Dagstuhl (2006)
2. Dagienë, V., Skûpienë, J.: Learning by competitions: Olympiads in Informatics as a tool for training high grade skills in programming. In: Boyle, T., Oriogun, P., Pakstas, A. (Eds.): 2nd International Conference on Information Technology: Research and Education, London, 28 June - 1 July, 2004. London Metropolitan University (2004) 79–83
3. Grigas, G.: Investigation of the relationship between program correctness and programming style in Informatica, vol. 6, No. 3 (1995) 265–276
4. IOI, International Olympiad in Informatics (2006) http://www.IOInformatics.org/
5. Kernighan, B. W., Pike, R.: The Practice of Programming. Addison-Wesley (1999)
6. LOI, Lithuanian Olympiad in Informatics (2006) http://ims.mii.lt/olimp/
7. Miara, R.J., Musselman, J.A., Navarro, J.A., Shneiderman, B.: Program Indentation and Comprehensibility in Communications of the ACM, vol.26, nos.11 (1983) 861–867
8. Mohan, A., Gold, N.: Programming Style Changes in Evolving Source Code. In: IEEE Proceedings of the 12th International Workshop on Program Comprehension, Bari, Italy, June 24–26, 2004 (2004) 236–240
9. Oman, P., Cook, C.: A taxonomy for programming style in 18th ACM Computer Science Conference Proceedings (1990) 244–247
10. Verhoeff, T.: The 43rd International Mathematical Olympiad: A Reflective Report on IMO 2002 in Computing Science Report 02-11. Faculty of Mathematics and Computing Science, Eindhoven University of Technology (2002)
11. Verhoef, T.: The I is (not) a science Olympiad. In: Perspectives on Computer Science Competitions for (High School) Students. Dagstuhl (2006)
«
atgal