Redirected
retagged by
2,179 views
2 votes
2 votes

There are n white dots and n black dots. Equally spaced in a line. You want to connect each white dot with some block dot in one to one fashion with a minimum total length of wire.
Consider 2 examples:

 

Greedy algorithm gives optimal solution for

  •  Only (i)

     

  • Only (ii)

     

  • Both (i) and (ii)

     

  • None of these
retagged by

2 Answers

Best answer
7 votes
7 votes
Solve for optimal solution without changing the sequence given in 1 and 2.

For optimal, Leftmost black dot should be matched with the leftmost white dot.

Total length of wire for 1st case according to greedy will be

(1,3)=2

(2,5)=3

(4,6)=2

total length=2+3+2=7

Total Length of wire for 2nd case according to greedy will be

(1,3)=2

(2,4)=2

(5,7)=2

(6,8)=2

total length=2+2+2+2=8

So 1st gives optimal.
selected by

Related questions

0 votes
0 votes
1 answer
2
Na462 asked Apr 30, 2018
4,368 views
Consider the following message:The number of bits required for huffman encoding of the above message are __________?My Strategy:- But the answer given is 52bits i used st...