Author |
Topic: Select The Right Person (Read 2463 times) |
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender: 
Posts: 236
|
 |
Select The Right Person
« on: Jul 12th, 2005, 3:53am » |
 Quote  Modify
|
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
|
| « Last Edit: Jul 15th, 2005, 7:20am by A » |
 IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Select The Right Person
« Reply #2 on: Jul 12th, 2005, 3:53pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Select The Right Person
« Reply #3 on: Jul 13th, 2005, 10:47am » |
Quote Modify
|
on Jul 12th, 2005, 3:53pm, Grimbal wrote:| 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). |
|
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)
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Select The Right Person
« Reply #4 on: Jul 15th, 2005, 4:06am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Select The Right Person
« Reply #5 on: Jul 15th, 2005, 7:17am » |
Quote Modify
|
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. ? 
|
| « Last Edit: Jul 15th, 2005, 7:19am by A » |
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
arvindbatra
Newbie
Posts: 1
|
|
Re: Select The Right Person
« Reply #6 on: Aug 16th, 2005, 10:04pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
eenampicchi
Newbie
Posts: 10
|
|
Re: Select The Right Person
« Reply #7 on: Nov 18th, 2007, 7:37pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print