Consider the following example: There were four quizes given in a course, worth 10, 10, 10, and 100 points respectively. Suppose a student got 10, 6, 6, and 70 points on these quizes respectively. Let us write this situation as "10/10, 6/10, 6/10, 70/100". Dropping the two quizes that the student got the lowest percentage on would result in dropping the "6/10, 6/10" quizes so his final quiz grade would be "(10 + 70)/(10 + 100)" (approximately 0.72). On the other hand, if the student drops one "6/10" quiz and the "70/100" quiz, his final quiz grade would be "(10 + 6)/(10 + 10)" (which is 0.8). Thus, dropping the lowest percentile quizes is not always the best strategy.

How might we go about writing an algorithm to determine which are the best quizes to drop? A tempting idea would be to greedely drop whichever quiz would be most beneficial, and then repeat this once more. This algorithm would run in linear time as a function of the number of quizes that were given. Surprisingly, this is no always the best strategy. The following is an example (discovered by Russell Ricks): suppose a student gets the quiz grades "85/100, 85/100, 6.99/20, 1000/1000". Using the greedy algorithm, the 6.99/20 quiz would be dropped first, followed by one of the 85/100 quizes. However, the best score is obtained by dropping both the 85/100 quizes at the same time.

python QuizDropper.py quizes.txtAn example "quiz" file is