Hospitals on a road: You are given  villages situated along a highway. Let x1, x2,x3 ....  xn represent the positions of these villages on the highway (the highway is a straight line). We need to build hospitals in k of these villages. Let di denote the distance from the i-th village to the nearest hospital, and let  be the sum of these distances. Our goal is to minimize D.

(a) Give an efficient algorithm to solve the problem fork = 1 and explain why it works. (Hint: Median) (3 pts)

(b) Consider an optimum placement for some k. Prove that thisoptimum

solution can be viewed as consisting of two optimum solutionsfor smaller problems,

where one problem is optimum placement of k - 1hospitals to cover some villages

and the other problem is placing a single hospital to cover therest of the villages.

State the "smaller problems" completely. (4 pts)

(c) Give a polynomial time algorithm to find the smallestpossible value of D

for a given k. (3 pts.)

D= D = i=1 di