GATE CSE
First time here? Checkout the FAQ!
x
0 votes
259 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.8k points)   | 259 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.5k points)   | 53 views
0 votes
1 answer
3
asked in Algorithms by Sarvottam Patel Junior (929 points)   | 59 views


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users