Problem 1 (i.e. 4.12) (max score = 20 points)
Part a:

1 point: a counter-example in which b_i > r.t_i for some i

2 points: showing that a valid schedule exists for the above counter-example.
To receive 2 points, you must provide a valid schedule and say why it is
valid. If an incomplete justification is shown, only 1 point.


Part b:

2 points: clearly presented algorithm
 if algorithm is not clearly presented, 1 point
 if no algorithm is presented, 0 points

3 points: analysis of running time
 should be O(n) for full credit
 only 1 point for O(nlogn) algorithm

2 points: (valid schedule exists) ==> (algorithm says "yes")
 if proof has minor error(s), only 1 point

10 points: (algorithm says "yes") ==> (valid schedule exists)

For this, apply the following scheme:

10 points: perfect solution, no errors

9 points: minor errors (e.g. typos, < instead of <=, etc.)

8 points: missing details on simple (but not obvious) cases

7 points: error in small portion of proof OR subtle mistake in proof

5 points: overall correct proof but "I don't know" for some part; minor
errors may be present

3 points: overall correct proof but "I don't know" for some part; at
least one important error

0 points: two or more important errors


Problem 2 (i.e. 4.13) (max score = 12 points)

I expect all correct solutions to be: sort by w_i/t_i (or reciprocal),
argue that an inversion exists, show that solution quality can be improved
by inverting the inversion.

2 points: clear description of algorithm
 deduct 1 point for each important detail that is unspecified

3 points: analysis of running time
 it must be O(nlogn) -- anything else gets a 0

5 points: argument that inversion exists
 appealing (correctly) to lecture notes/textbook is OK
 if appeal to other sources, must restate in own words
 (0 points for simply citing any other external source)
 deduct 1 point if there are minor errors
 deduct 4 points if there are major errors

2 points: math showing exchange improves solution quality
 deduct 1 point if errors exist 


Problem 3 (i.e. 4.14) (max score = 13 points)

Part a:

Algorithm description:

1 point: algorithm sorts finish-times in increasing order (variants
possible)

1 point: algorithm iteratively selects jobs, scheduling status_check at
finish times

1 point: algorithm eliminates all jobs that overlap with this job

1 point: algorithm does something smart to achieve this quickly

Running time analysis:

1 point: O(nlogn) time to sort

2 points: analysis of "smart" operation to find overlaps
 deduct 1 point for "non-smart" method with O(n^2) analysis
 deduct 2 points for "non-smart" method without O(n^2) analysis

Correctness:

1 point: prove that algorithm covers all jobs

Part b: 5 points
 5 points: proof that k* status_checks suffice
 0 points if they show k* checks are necessary
 deduct 1 point if minor errors exist
 deduct 4 points if major errors exist