• retagged by
3,731 views
2 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

2 Answers

Best answer
7 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
Position:
Show:

Related questions

0 0 votes
1 1 answer
1.5k
1.5k views
Na462 asked Apr 30, 2018
1,461 views
Consider the following graph:If the edge weight of minimum spanning tree are given and edge weight of each edge is distinct, then the minimum value of sum (a, b, c, d, e,...
0 0 votes
1 1 answer
5.6k
5.6k views
Na462 asked Apr 30, 2018
5,558 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...
2 2 votes
4 4 answers
5.8k
5.8k views
Pankaj Joshi asked Jan 22, 2017
5,756 views
The optimal time required in merging the list of size 11, 21, 33, 34,45,54,60 ismy answer (11+21)*4+ 33*3 +(34+45)*3 + (54+60)*2but the provided answer is 269 to 282I don...
6 6 votes
3 3 answers
28.6k
28.6k views
Akash Kanase asked Dec 1, 2015
28,572 views
What is the time complexity of job sequencing with deadline using greedy algorithm?O(n)O(log n)O(n log n)O(n2)Made EasyFull Syllabus Test-6 : Basic Level : Practice Test-...