teachers best friend

[luby]

There's this algorithem here about if a teacher allows you to drop 1(or more) test grade in order to maximized your grade. This is supposed to let you do that. I cannot understand it, as i do not get the complex math stuff. If i could get it explained in english i might be able to program it.
thanks.

[DarkerLine]

This is actually very theoretical; for practical purposes, a teacher will drop grades that all have the same weight (in most cases) and in the few cases where they don't, brute force works because there aren't too many grades being dropped. However, the problem itself is interesting.

I'm also afraid the paper is as simple an explanation as you're likely to get. There are two steps to solving this problem:

1. Find an efficient way to calculate some function F(q) where q is a number 0 to 1. Don't worry about what it means, but we calculate it as follows:
a. Calculate f_j(q) = (Points Earned) - q*(Points Possible) for each individual assignment.
b. Find the (# of assignments not dropped) of assignments for which this value f_j(q) is maximized.
c. Add up the f_j(q) for all of these assignments. This is F(q).

2. Use Newton's Method to find the zero of F(q). The paper shows that this will give us the answer; for now, just take this for granted.

a. The formula for Newton's method, we know, is x_n+1 = x_n - F(x_n)/F'(x_n). We need to find a way to find a derivative of F.

b. Fortunately, F is piecewise linear. That means if we take values q' that are close to q, F will be straight between q and q' and we just find the slope between these two points.

c. How close is close enough? The paper shows that at slope changes, the denominator of q is at most (# of assignments not dropped)*(maximum points possible for any assignment). We need to square this denominator's reciprocal to get the number we can safely add to q to get q'.

Now we just iterate until we find a q for which F(q) is 0. Then we take the optimal assignments found in step 1 for this q, and these will be the assignments we don't drop.