__Problem corrections and clarifications for Final Exam:__

__Question 2:__ You only need to produce the graph and the way to interpret the answer. You do not actually need to *solve *the resulting MIS problem.

__Question 3:__ You may NOT assume that the numbers are given in sorted order.

__Question 5:__ The length of *each* gap must be at most 1. The total length of all gaps might be much larger if say you had 20 gaps each of length 1/2.

__Question 6:__ The last sentence of the hint should read: "Thus
minimizing max(w_1(T), w_2(T)) will involve finding a tree with w_1(T) =
w_2(T)."