wu :: forums
« wu :: forums - Universal Sink »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 1:45am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, Eigenray, Grimbal, towr, ThudnBlunder, william wu, SMQ)
   Universal Sink
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Universal Sink  (Read 12071 times)
johny_cage
Full Member
***





   


Gender: male
Posts: 155
Universal Sink  
« on: Nov 18th, 2007, 3:05am »
Quote Quote Modify Modify

You are having a directed graph G contains a universal sink (a vertex with in-degree |V|-1 and out-degree 0). Now, you have to find this universal sink in O(V).
And the scheme used is adjacency matrix.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Universal Sink  
« Reply #1 on: Nov 18th, 2007, 7:07am »
Quote Quote Modify Modify

Check every vertex to see if it has out-degree 0, only the sink has that.
But, in an adjacency matrix, that would take O(V2)
So I suppose there must be some cleverererderder more clever way..
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
johny_cage
Full Member
***





   


Gender: male
Posts: 155
Re: Universal Sink  
« Reply #2 on: Nov 18th, 2007, 8:22am »
Quote Quote Modify Modify

Yups, i m also thinking, there should be some way to do it in O(V)....
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Universal Sink  
« Reply #3 on: Nov 18th, 2007, 11:12am »
Quote Quote Modify Modify

i=j=0
while( j<n ){
  if( there is an edge from i to j ) i++;
  else j++;
}
-> the universal sink is i.
« Last Edit: Nov 18th, 2007, 12:18pm by Grimbal » IP Logged
johny_cage
Full Member
***





   


Gender: male
Posts: 155
Re: Universal Sink  
« Reply #4 on: Nov 18th, 2007, 11:32am »
Quote Quote Modify Modify

hey Grimbal,
 
plz elaborate your answer more, as what is i and jHuh
and if u want to say i and j are vertices then please tell how they are going to initialize, and what if there exist no [bold]Universal Sink[/bold]. Then, the while loop used never terminate....
 
so, please elaborate your answer....
« Last Edit: Nov 18th, 2007, 11:32am by johny_cage » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Universal Sink  
« Reply #5 on: Nov 18th, 2007, 12:15pm »
Quote Quote Modify Modify

on Nov 18th, 2007, 11:32am, johny_cage wrote:
what if there exist no Universal Sink. Then, the while loop used never terminate....
If there is no universal sink, then the premise of the problem is broken. (It is stated G does contain a universal sink)
 
But you can add a condition to break when i n
Because either the loop ends normally, or i will increase beyond n.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Universal Sink  
« Reply #6 on: Nov 18th, 2007, 12:17pm »
Quote Quote Modify Modify

i and j are vertices.  I assumes vertices are numbered from 0 to n-1
 
The problem says "You are having a directed graph G contains a universal sink".  So I ignored the case where there is in fact no universal sink.
 
What I called "a link from i to j" is a directed edge starting at i and ending at j.
 
Maybe it is clearer if you consider the adjacency matrix where aij=1 if there is an edge from i to j, 0 if not.  The problem is then to locate the row s consisting of only zeros, knowing that column s has only ones, except for ass.  The algorithm ends with i=s because it cannot end larger than s and it cannot end smaller than s.  i cannot end larger than s because once it reaches s it can not increment any more.  i can not end smaller than s, because when j reaches s, i will be incremented until i=s.
« Last Edit: Nov 18th, 2007, 12:20pm by Grimbal » IP Logged
aditi
Newbie
*





   


Posts: 17
Re: Universal Sink  
« Reply #7 on: Nov 18th, 2007, 7:26pm »
Quote Quote Modify Modify

nice solution
IP Logged
swami
Newbie
*





   
Email

Gender: male
Posts: 17
Re: Universal Sink  
« Reply #8 on: Nov 26th, 2007, 4:58am »
Quote Quote Modify Modify

I am not clear with this soln.
 
Suppose 'i' got incremented last when j=j1 after which 'i' did not change.  'i' is outputted as the universal sink.  But the algo. doesnt seem to check incidence from 'i' to j<j1
 
Am i missing something? Can someone throw some light on this?
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Universal Sink  
« Reply #9 on: Nov 26th, 2007, 8:00am »
Quote Quote Modify Modify

It doesn't check that there is one.  The only claim is that if there is an universal sink, then it finds it.
 
If there is no universal sink, it might return anything, even crash on an array index out of bounds.
 
But it is a given that there is one, so I don't really have to verify it.
 
You could check whether i exceeds the bounds (in which case there is no universal sink) and do a second pass to check that the returned node is indeed an universal sink.  It would still be O(n).
IP Logged
swami
Newbie
*





   
Email

Gender: male
Posts: 17
Re: Universal Sink  
« Reply #10 on: Nov 26th, 2007, 8:52am »
Quote Quote Modify Modify

No...My doubt is this
 
    1 2 3 4 5  
1  1 0 0 0 0  
2  0 0 1 0 0
3  1 0 0 0 0  
4  0 0 0 0 0
5  0 0 0 0 0
 

The algo will return '3' as the universal sink, while '4' or '5' shud have been the answer.
« Last Edit: Nov 26th, 2007, 9:38am by swami » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Universal Sink  
« Reply #11 on: Nov 26th, 2007, 9:29am »
Quote Quote Modify Modify

on Nov 26th, 2007, 8:52am, swami wrote:
The algo will return '3' as the universal sink, while '4' or '5' shud have been the answer.
Neither 4 nor 5 or universal sinks as per the definition.
In fact following the definition given, there can be at most one universal sink, because all nodes (other than itself) must link to it, and it mustn't itself link to any nodes.
If there are two sinks, neither can link to the other, and so neither can be universal.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
swami
Newbie
*





   
Email

Gender: male
Posts: 17
Re: Universal Sink  
« Reply #12 on: Nov 26th, 2007, 9:37am »
Quote Quote Modify Modify

OK.. gotit...sorry abt that  
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board