Assume that you are given n white and n black dots, lying on a line, equally spa
ID: 3822710 • Letter: A
Question
Assume that you are given n white and n black dots, lying on a line, equally spaced The dots appear in any order of black and white, see the example picture below. We need an algorithm which connects each black dot with a (different) white dot, so that the total length of wires used to form such connected pairs is minimal. The length of wire used to connect two dots is equal to their distance along the line. (a) Someone has proposed the following algorithm: start by connecting the closest pair of a black and a white dot. Repeat. Give an example where such an algorithm fails to produce an optimal solution. (b) Design an algorithm which produces an optimal solution.Explanation / Answer
a) The given algorithm may not be always optimal solution because the algorithm will always iterate over the array and pair each black dot with the first white dot which may not be suitable for every array and may give bigger total distance.
b) The second approach of matching opposite dots can be like, If the white and lack dots are sorted then we can match the ith black dot with the ith white dot . This solution can be proved to be optimal because by matching leftmost dot with the left most dot of the opposite colour there will be no loss of generality.
Suppose we match by the solution given as, W0 to some black dot Bi and then the leftmost black dot B0, to Wj, Then we can compute the cost of matching pairs as,
C(W0,Bi)+C(Wj,B0)=BiW0+|WjB0|