wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Select The Right Person
        
(Message started by: R0B1N on Jul 12^th, 2005, 3:53am)

Title: Select The Right Person
Post by R0B1N on Jul 12^th, 2005, 3:53am

In a Group of N people how will u identify

(i)a person who knows all others

(ii)a person who is known to everyone

(iii)a person who knows everyone and who is known to everyone

(iv)a person who does not know anyone and no one knows him

The only Function you can use is
bool IsKnown(i,j) which returns true if i knows j else false
(Edit 2 :- This function Takes O(1) Time )

you are required to find O(n) algorithm

EDIT::
(v) Person who is known to everyone , But who does not know anyone

(vi) Person who knows everyone , but no one knows him

Title: Re: Select The Right Person
Post by towr on Jul 12^th, 2005, 10:14am

hmm. I never was very good with graphs..

Title: Re: Select The Right Person
Post by Grimbal on Jul 12^th, 2005, 3:53pm

I wonder. (i) and (ii) are like finding a row or a column in a binary nxn matrix that has all bits set in a row or a column. You really cannot do it in O(n). To find a row of all ones, when almost all bits are set, you must test each row. If all but one cell is one, you have to check on average n/2 cells. That is O(n^2).

Title: Re: Select The Right Person
Post by R0B1N on Jul 13^th, 2005, 10:47am

on 07/12/05 at 15:53:53, Grimbal wrote:

Hi Grimbal

i think problem (vi ) is similar to finding a universal sink in a graph , which can be done in O(n) time , given the adjacency matrix

solution to (vi) also a solution to (ii)
solution to (v) also a solution to (i)

Title: Re: Select The Right Person
Post by Grimbal on Jul 15^th, 2005, 4:06am

Depends how you store your relations.
Given an X, to find an Y such that X knows Y, you can do it in O(1) if you have for everybody the list of the people he knows. But if you have a boolean matrix, it is O(n).

Title: Re: Select The Right Person
Post by R0B1N on Jul 15^th, 2005, 7:17am

Grimbal ,
Do u mean to say u have O(V) algorithm to find Universal Sink ? :-/
The Problem of universal sink is a exercise problem in the book "Introduction to algorithms" by Cormen.

Do u have O(N) algorithms if Boolean Matrix is Given. ? ::)

Title: Re: Select The Right Person
Post by arvindbatra on Aug 16^th, 2005, 10:04pm

hi!
this is my first post.

can any one give the solution of finding an universal sink in O(n) time when a boolean adjacency matrix is given

i read this problem in Coremen

my best shot is O(n^2)
are we supposed to use some auxillary datastructure other than adjacency matrix to get an o(n) solution???

Title: Re: Select The Right Person
Post by eenampicchi on Nov 18^th, 2007, 7:37pm

Finding a person who doesnt know anyone but is known to everyone is called the "celebrity problem".

Can be solved like this:
From the set of n people, choose any two A and B. As A : Do you know B?

If A knows B, A cant be the celebrity. If A does not know B, B cant be the celebrity. So with every question we eliminate at least one person. So in n questions we reduce the number of ppl to be considered for celebrity status to 1.

After identifying the person, ask every one else if they know the celbrity. If everyone says yes, he is celebrity. Else no one is.

Each round here takes O(n) time.

For the next part, where we need to find someone who knows everyone but is not known to anyone :

Again proceed the same way, but this time as the questions :

To A : Do you know B ?
if yes, B is not the person.
if no, A is not the person.

Again we eliminate one person per question asked.

Does that solve things?