Testing of programs with random generated test cases

From IOI Wiki
Jump to: navigation, search
Pub article.png

Abstract: Testing of computer programs is an essential part of the evaluation process of a programming contest. It is a mix of functional and non functional testing and a specific case of the "black box" testing well known from the domain of Software engineering. The paper discusses one of the possible forms of creating test cases for a program that implement an unknown algorithm - the random generation of test cases - and the problems that could arise when random generated test cases are used for evaluation of programs submitted by participants in programming contests. Rooted trees were chosen for the start of the research because of their simplicity. More deep problems and more interesting results could be expected for general graphs and other combinatorial objects.

Keywords: program testing, functional and non functional testing, "black box" testing, graphs, rooted trees, random generation, height, width and branching statistics of rooted trees

Download: http://www.mii.lt/olympiads_in_informatics/htm/INFOL055.htm (free)