Testing Problems
|
| Testing Problems
|
One of the goals of our programming contest has always been to engage students in challenging problems that present real programming experiences. Originally this was done exclusively through traditional programming contest problems and even today such problems comprise the majority of our contest. About ten years ago, we became concerned that nothing in the contest forced the students to wrestle with the concept of a class. Starting in 2000, we introduced “Class-based problems”; these problems emphasize the understanding of abstraction and require the students to be able to read the specifications for a class and to use a class (that is new to them) based only upon those specifications and without being able to view the source code of the class. More recently, we have seen some evidence that students need to test their work more thoroughly; hence our desire to create a problem that requires more extensive testing.
Over the past decade, the role of testing in software development has grown significantly. Certain methodologies, such as test-driven development, have even elevated it to a pre-eminent position among a programmer’s tasks. Tools such as JUnit have been developed to facilitate all sorts of automated testing; many of these tools are now built-in to development environments. The result, in general, has been higher quality software. Often, in the “olden days”, the discovery of a test that caused a program to fail was viewed as a sad occasion; now such discoveries are expected as part of the development of a high-quality software product. It is our goal to incorporate such work, such discoveries, and their attendant rewards into our programming contest.
The specific motivations for our testing problems are two-fold. One is the great improvement in software quality that we have seen as a result of having our own students code JUnit tests during lab exercises. The other is the approaches we have seen used during the challenge phase of TopCoder’s algorithm contests. Both of these testing environments represent a cross between black-box and open-source testing. For our contest we wished to emphasize the abstraction approach of black-box testing. We could have simply had students write JUnit tests, but this had two drawbacks: 1)it would force many students to use a new technology (JUnit) along with its attendant syntax, and 2) it would be particularly unfair to teams whose expertise is primarily in C++. We thus strove to create a testing experience that was language independent.
For a testing problem, students will be presented with a set of specifications that is equivalent to those given for any other problem. The background information will be given, followed by a specific problem description, verbal descriptions of the input and output, and finally a small number of specific examples. The expectations about input are the same; it is assumed that all input is in the proper format. (Thus, a team that drives a bug through the use of input that does not meet the specifications will not be credited with a correct submission.) As with more traditional problems, students will be able to ask questions if the specifications appear unclear; they will also be limited to only one submission per testing problem. The only difference lies in the scoring. Programming Problems are now worth two points apiece; Testing Problems are worth only one point each.
For a testing problem students will be given a link to a web page that features forms for input as well as two buttons. The Execute button will cause the judges' (buggy) solution to run; the Submit button will start the submission process. When the Execute button is clicked, the judges' (buggy) solution will run on the data specified in the input form. The result will be displayed on the page. Once a team is ready to submit, they will place the input that drives the bug into the first form. They will click the Execute button to place the (bogus) output into the output form. They will also place the correct output (for their given input) into a third form. Clicking the Submit button will cause both their input and their claimed output to be sent for judging.
Two sample problems are linked at the bottom of this page.
Obviously, we could make these problems impossible to solve. We could write our solution so that only an input of 77.02743 will drive the bug. This would clearly be unfair. While one can always debate the meaning of the word “natural”, our promise is that we will incorporate only “natural” bugs into these programs. In the case of the 2007 contest, each solution, including the sample below, exhibits bugs that we have seen arise multiple times as various programmers have attempted to solve these same problems. While we have rewritten those solutions (often from scratch), the bug(s) chosen came from these observations.
Our programming contest prohibits the use of external calculators (although the Windows calculator is available). A correct submission requires that the team in question include the correct output along with their submission. Therefore we have endeavored to ensure that the discovery of the bug does not require complex arithmetic computations. We do not expect that teams will perform square roots or trigonometric functions in their head; nor do we expect them to add up large columns of numbers, or test the program on data sets which take a significant amount of time to type or read.
To help avoid confusion, we promise that our program will work correctly on the examples given in the specifications.
The bug will never (deliberately) be a trivial misspelling, punctuation, or formatting error. Likewise, our bug will never (deliberately) cause the solution to crash or to go into an infinite loop. Should a team discover such a case, it could, of course submit it.
This being the first year that we included Testing Problems, no one has yet solved one under “competition conditions”. Still, we believe that there are certain strategies that are likely to succeed. In particular, students should read the specifications carefully and should test those situations that cover all contingencies outlined therein. Particular attention should be shown to boundary conditions as well as to “danger” cases such as a zero in the denominator of a fraction, a negative number that might be used as an argument to a square root function.
We obviously have limited experience with these problems, but we do have some expectations. Submissions are required to have the program’s answer differ from the claimed correct answer. We thus anticipate that the bulk of incorrect submissions will occur because the team has miscomputed the correct answer for the given input. Teams should check carefully for typos in each of the forms.
We have developed two sample problems so that teams may become familiar with the problem type. The first, Addition, is meant to acquaint teams with the mechanisms of the new Challenge Problems. The second, Rock, Paper, Scissors, is a more typical problem in terms of complexity and the degree of difficulty of finding the bug.
In both cases, the Submit button is validating that the forms contain data, but is NOT checking that the data is in the correct form. It is up to the team to verify that its input and output are in the correct form! This is true for both these advance problems and for the problems used during the contest. Note that the web pages for the advance problems do not verify that the input is in correct format; therefore it is possible to get a "submission correct" message by entering illegal data. Entering illegal data during the contest will result in a submission being judged as incorrect. (Thanks to an anonymous contestant for pointing out this flaw.)
After clicking the Submit button while solving these problems, teams will receive feedback about the correctness of their submission. During the contest, teams will not receive this feedback, but will be presented with a "confirmation page" to guard against accidental submissions.