search
Log In
0 votes
275 views
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?
in Algorithms 275 views
0
A different type indeed :P

1 Answer

1 vote
 
Best answer

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
0
IES level solution :p #the_end i dont think anyone will ever have doubt from this topic now :p
0

arvin hehe :P :P

0
Waao, @minipanda, can you tell total number of topological orders possible?
0
Won't it be 4..that is all those 7 length paths mentioned?
0
You have taken 1 instead if we take 4, there will be more orders

Correct me?
0

Rishav Kumar Singh yes you are right.. I am getting too many orders now >:(  Getting hard to calculate.. how much did you get?

0
I left, by the time I found it so complex.
0
haha :P  I don't think so many nodes will be given during exam for finding topological order..even if there are many nodes, their in degrees shouldn't be too close to each other :p

Here after visiting one node the in degrees of so many other nodes are getting affected opening ways for so many orders!! -_-
0
You are right. I agree

Related questions

0 votes
0 answers
1
335 views
Suppose we modify mergesort as follows. We split the input into three equal segments, recursively sort each segment and then do a three way merge of the three sorted segments to obtain a fully sorted output. If we work out the recurrence for this variant, we find that ... of usual mergesort. d)This depends on the length and the initial arrangement of values of the input. answer given is b.Why?
asked Aug 23, 2018 in Algorithms amitqy 335 views
0 votes
1 answer
2
204 views
Consider the following two statements: 1. If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) is O(h(n)) 2. If f(n) is O(h(n)) and g(n) is O(h(n)) then either f(n) is O(g(n)) or g(n) is O(f(n)) Why is second statement false?
asked Aug 21, 2018 in Algorithms amitqy 204 views
3 votes
2 answers
3
400 views
Degree of concurrency in threads can be arranged in the manner One-to-one > many-to-one > many-to-many One-to-one > many-to-many > many-to-one Many-to-many > many-to-one > one-to-one None of the above answer given is A but according to me answer is B. Someone please confirm
asked Sep 7, 2020 Akanksha Agrawal 400 views
1 vote
2 answers
4
337 views
is given ans correct ?
asked Aug 31, 2020 in Digital Logic Sanjay Sharma 337 views
...