GATE CSE
First time here? Checkout the FAQ!
x
0 votes
271 views

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
asked in Algorithms by Loyal (3.9k points)   | 271 views
What does it mean by total length of wire?
Yes i have the same querry and problem

How to solve it please tell >???????
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=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=8

So 1st gives optimal.

1 Answer

0 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.
answered by Loyal (2.9k points)  

Related questions

0 votes
1 answer
2
asked in Algorithms by LavTheRawkstar Boss (5.6k points)   | 68 views
0 votes
1 answer
3
asked in Algorithms by Sarvottam Patel Junior (929 points)   | 68 views


Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1616 Points

  3. sh!va

    1580 Points

  4. Arjun

    1336 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1028 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    972 Points

  9. LeenSharma

    810 Points

  10. srestha

    662 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    242 Points

  2. Ahwan

    138 Points

  3. joshi_nitish

    112 Points

  4. jjayantamahata

    104 Points

  5. Arjun

    64 Points


22,725 questions
29,056 answers
65,053 comments
27,566 users