COT 5407: Introduction to Algorithms
Fall 05
Frequently Asked Questions

Oct 11:

Question: "Oil of Olay" has me stumped. Can we get a hint on Problem #20 (Ex 9.3-9, p193)?
Answer: Your problem is to decide on the y-coordinate of the large east-west pipeline. Supposing this y-coordinate is Y₀, then you want to minimize the sum of the differences between Y₀ and the y-coordinates of each of the wells. The wells can be divided into two sets: the ones that are above the large pipeline (i.e., y-coordinate of well is greater than Y₀) and the ones that are below the large pipeline (i.e., y-coordinate of well is smaller than Y₀). As a warm up, try to explain why you would not build the large pipeline above the oil well with the highest y-coordinate (what happens to the sum of the lengths of the spur pipelines when you move the large pipeline south by a small amount (say &epsilon)?). Now ask yourself what should be the value of Y₀ so that moving the large pipeline north or south would increase the sum of these lengths and why? Your answer needs to be justified or argued out.

---

Oct 12:

Question: Does the answer to this problem, i.e., Problem #20 (Ex 9.3-9, p193) involve finding the median?
Answer: Even if it is, you need to proved (or argue it out) using the strategy outlined above.

---