retagged by
1,153 views
0 votes
0 votes
10 rooms, numbered 1 to 10, need to be rewired, but there are constraints on the order in
which this can get done.
Rooms 5 and 8 must be rewired before starting on 6
Room 1 must be rewired rewired before starting on 7 and 9
Rooms 4 and 5 must be rewired before starting on 2
Rooms 8 and 10 must be rewired before starting on 5
Room 3 must be rewired rewired before starting on 1 and 4
Rooms 9 and 7 must be rewired before starting on 10
Rooms 9 and 10 must be rewired before starting on 8
Rewiring a room takes one full day. In a day, any number of rooms can be rewired simultaneously
provided the constraints above are met. What is the minimum number of days required to complete the
rewiring?

a)  10

b)   9

c)   8

d)   7

 

In the solution they have drawn a DAG from this and then finded the longest paths.

"Longest paths are 3-1-9-10-8-5-2, 3-1-7-10-8-5-6, 3-1-9-10-8-5-6 and 3-1-7-10-8-5-2 each of length 7." <--quoted from answer

How is it done?How is it connected to DAG?
retagged by

1 Answer

Best answer
1 votes
1 votes

I have done it by topological sorting method..

I am going to explain it by table because drawing diagram might make it dirty. But I will suggest you to draw it on your own following the steps mentioned. Then it will be very easy for you to understand. Refer the table for verification purpose.

1. Create 10 nodes.

2. Draw a directed edge b/w the node u->v if v is dependent on u. For eg: " Rooms 8 and 10 must be rewired before starting on 5 " Here we have to draw an edge directing from 8 and another directed edge from 10 to node 5.

3. After making all the edges note down the in-degree of each node i.e. no. of edges directing to a node.

I got :

in_deg(1) 1 (directed from 3)
in_deg(2) 2 (directed from 4 and 5)
in_deg(3) 0
in_deg(4) 1 (directed from 3)
in_deg(5) 2 (directed from 8 and 10)
in_deg(6) 2 (directed from 5 and 8)
in_deg(7) 1 (directed from 1)
in_deg(8) 2 (directed from 9 and 10)
in_deg(9) 1 (directed from 1)
in_deg(10) 2 (directed from 7 and 9)

 

4. Now you can see that node 3 is the only independent node. It does not depend on any other node (indeg(3) =0). This means that before rewiring room no. 3 no other room needs to be rewired.

So start with 3 and cancel all the edges that originated from node 3. They are 1 and 4. So the indeg of 1 and 4 are reduced by 1.

What does this mean? Room no. 1 and 4 can be rewired only after 3 is done. [Point no. 5 in the list you gave ]

Now update the indeg of node 1 and 4.

in_deg(1) 1-1=0
in_deg(2) 2
in_deg(3) 0
in_deg(4) 1-1=0
in_deg(5) 2
in_deg(6) 2
in_deg(7) 1
in_deg(8) 2
in_deg(9) 1
in_deg(10) 2

 

Now since in degree of 1 and 4 are 0 it means they are now independent of any other node. Both can be processed simultaneously because it is given that :

 In a day, any number of rooms can be rewired simultaneously provided the constraints above are met.

So, till now 3,(1,4) are rewired.

5. Now update the table again and change the in degrees of those that that were dependent on 1 i.e. 9 and 7 and on 4 i.e. 2.

in_deg(1) 0
in_deg(2) 2-1=1
in_deg(3) 0
in_deg(4) 0
in_deg(5) 2
in_deg(6) 2
in_deg(7) 1-1=0
in_deg(8) 2
in_deg(9) 1-1=0
in_deg(10) 2

 

So in deg of 9,7 are 0 now. They can be processed simultaneously.

So, till now 3,(1,4),(7,9) are rewired.

6. Again update the table by decreasing the in degrees of those nodes that were dependent on 2,7,9.

10 is dependent on 7. 8 and 10 are dependent on 9.

Hence in deg of 10 will be reduced by 2.

in_deg(1) 0
in_deg(2) 1
in_deg(3) 0
in_deg(4) 0
in_deg(5) 2
in_deg(6) 2
in_deg(7) 0
in_deg(8) 2-1=1
in_deg(9) 0
in_deg(10) 2-2=0

So now in deg of 10 is 0 and no other node has in degree=0. Hence 10 is the only independent node at this stage.

So, till now 3,(1,4),(7,9),10 are rewired.

After rewiring room 10 we can move to room 5 and 8.

Decrease their in degree by 1.

 

7. Update the table:

in_deg(1) 0
in_deg(2) 1
in_deg(3) 0
in_deg(4) 0
in_deg(5) 2-1=1
in_deg(6) 2
in_deg(7) 0
in_deg(8) 1-1=0
in_deg(9) 0
in_deg(10) 0

 

Only node 8 has in degree 0. So process it and reduce the in degree of nodes dependent on 8 i.e. 6 and 5.

So, till now 3,(1,4),(7,9),10,8 are rewired.

8. Update the table :

in_deg(1) 0
in_deg(2) 0
in_deg(3) 0
in_deg(4) 0
in_deg(5) 1-1=0
in_deg(6) 2-1=1
in_deg(7) 0
in_deg(8) 0
in_deg(9) 0
in_deg(10) 0

 

Now only in degree of 5 is 0. 2 and 6 are dependent on 5. Reduce in degree of 2 and 6 by 1.

So, till now 3,(1,4),(7,9),10,8,5 are rewired.

9. Update the table :

in_deg(1) 0
in_deg(2) 1-1=0
in_deg(3) 0
in_deg(4) 0
in_deg(5) 0
in_deg(6) 1-1=0
in_deg(7) 0
in_deg(8) 0
in_deg(9) 0
in_deg(10) 0

 

Now 2 and 6 can also be processed.

So, till now 3,(1,4),(7,9),10,8,5,(2,6) are rewired.

If you notice the order, 7 days are needed to complete rewiring.

3 on 1st day. (1 and 4) on 2nd day. (7 and 9) on 3rd day and so on...

Longest paths are 3-1-9-10-8-5-2, 3-1-7-10-8-5-6, 3-1-9-10-8-5-6 and 3-1-7-10-8-5-2 each of length 7.

Satisfied :)

End :P

selected by
Answer:

Related questions

2 votes
2 votes
1 answer
1
rsansiya111 asked Dec 8, 2021
832 views
Suppose we do merge sort with a three-way split: divide the array into 3 equal parts, sort each part and do a 3 way merge.What would the worst-case complexity of this ver...