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)."