Useful Scripts -->
Suppose you are teaching a class where you give your
students a quiz once a week to determine part of their grade.
Suppose that you let the students drop whichever two quizes
If every quiz is worth the same amount of points, then of course
students should drop their two lowest quizes.
Suppose, however, that not every quiz is worth the same amount.
That is, the total amount of points on each quiz is different
so each quiz is worth a different portion of their final grade.
In this case, a student may want to drop a quiz that is worth
a large number of points even if they got a relatively high
percentage on it.
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
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)"
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
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.
The python script
QuizDropper.py.txt performs the optimal
quiz dropping algorithmn (it drops whichever two quizzes will help
the student the most).
To run the program, put both QuizDropper.py.txt and
the same directory (remove the .txt extension from the QuizDropper)
and run the following command:
python QuizDropper.py quizes.txt
An example "quiz" file is quizes.txt.
The first line of a quiz file should include the total amount of
points that each quiz is worth.
The remaining lines should contain the first and last name of each
student followed by their score on each quiz.
It is important that there are no stray newlines in this file.