Optimal Algorithm (Puzzle)
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Optimal Algorithm (Puzzle)

  1. #1
    Join Date
    Apr 2009
    Posts
    14

    Optimal Algorithm (Puzzle)

    On a mountain there are two types of people - consistent and inconsistent. The consistent people always speak the truth, while the inconsistent people cannot be trusted (they may speak the truth or they may not). Now you go to the mountain to find all the consistent people. To do that you can ask a question to a person A regarding another person B the following way:

    "Is B a consistent person?" (this is kind of questions that you can ask to a person)

    Now if A is consistent then he will tell the truth. Otherwise the answer of A could be either true or false. Before you reach the mountain you realize that there are more consistent people than inconsistent people. I am looking for an algorithm using the example question shown above - to find out the number of consistent people. It is possible to do this in Big Theta (n).

    Thanks.

  2. #2
    Join Date
    Sep 2013
    Posts
    13

    Re: Optimal Algorithm (Puzzle)

    Quote Originally Posted by vsha041 View Post
    Before you reach the mountain you realize that there are more consistent people than inconsistent people.
    Given that the consistent people are in majority, the group of all people together will be consistent. The inconsistent vote of the minority isn't big enougth to change the consistent vote of the majority.

    So if everybody is asked about a specific person you will know for sure whether this person is consistent or not because what most people answer is the truth. By repeating this you will be able to locate a consistent individual eventually. This known to be consistent person can then be used to determine whether everybody else is consistent or not.

    Say there are N people. A voting requires N-1 people to be asked. The number of necessary votings depends on the fraction of consistent people among the N. This number is a constant of probabilistic nature (an expectation) independent of N. Finally to classify everybody requires N-1 questions to be asked.

    All in all this gives a linear dependency on N, that is the algorithm is O(N).
    Last edited by dazzle; September 19th, 2013 at 01:18 AM.

  3. #3
    Join Date
    Apr 2009
    Posts
    14

    Re: Optimal Algorithm (Puzzle)

    Thanks Buddy :-)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center