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) =