Help explaining test questions

This is a discussion on Help explaining test questions within the General Discussions forums, part of the Community Boards category; 1000 numbers are generated. If you take every four numbers as a sequence then you have 250 possible sequences where ...

  1. #16
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    1000 numbers are generated. If you take every four numbers as a sequence then you have 250 possible sequences where you could have four even numbers. There are actually 997 potential sequences, but the 250 is a subset of the total that is easier to work with. So if the odds are minuscule that none of the 250 groups are all even, then it means that the odds are even more minuscule that none of the 997 groups are all even.
    I think you are misunderstanding the question.

    Here's the question repeated:

    2) 1000 random integers are generated randomly with a uniform distribution over the range 1 to 1000 inclusive. Which of the following would indicate a poor generator?

    (a) the average of the numbers is about 499
    (b) each number appears exactly once
    (c) no four consecutive numbers are all even
    (d) two of the above
    (e) all of (a), (b), and (c)
    My interpretation: we have 1000 random samples. Each sample can have a numeric value between 1 and 1000. When we say "four consecutive numbers" we intend to mean "four numbers in order of which they were generated" and not "four numbers in numeric order from least to greatest or greatest to least".

    Every time a new random sample is generated, we look at the last 4 random samples. Are they all even? I would hope not! Sure, it might happen every once in awhile, but the chances are low. Hence, the wording of the answer:

    "NO four consecutive numbers are all even"

    Having no four consecutive numbers that are all even would be a good indicator that my random number generator is truly random. Having 1 or 2 sequences that are all even might even be fine as well. Having several sequences that are all even would be very very bad.
    My Website

    "Circular logic is good because it is."

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> Having no four consecutive numbers that are all even would be a good indicator that my random number generator is truly random.

    IMO, you're right about MK27's confusion, but the above is wrong. Depending on how you define it, you should expect around either 31 or 62 sequences of four consecutive even numbers when generating 1000 random numbers.
    Last edited by Daved; 11-09-2009 at 01:33 PM. Reason: bug in program meant wrong numbers in post

  3. #18
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Daved View Post
    IMO, you're right about MK27's confusion
    Yeah, I was considering the final set as ordered. You're right, it almost certainly should have sequences of 4 even numbers.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #19
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    You're right, it almost certainly should have sequences of 4 even numbers.
    True, in that point I do stand corrected.

    But...if it didn't...would it be a sign of a bad random number generator? I guess that's the question we have to ask ourselves.

    On a sidenote, I decided to play around a bit I wrote the following code:

    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int rand_num(int min, int max)
    {
    	return ((int)((rand() % max) + min));
    }
    
    int main ( void )
    {
    	srand(time(NULL));
    	
    	int num_even_sets = 0;
    	
    	//Generate a set of 1000 samples
    	vector <int> randomSet;
    	for(int i = 0; i < 1000; i++ )
    	{
    		randomSet.push_back(rand_num(1, 1000));
    	}
    	
    	//Go through and analyze for sequences of 4-evens
    	for (unsigned int i = 0; i < randomSet.size(); i++ )
    	{
    		bool even = true;
    		for(unsigned int j = i; j < (i + 4) && j < randomSet.size(); j++ )
    		{
    			if (randomSet[j] % 2 != 0) even = false;
    		}
    		
    		if (even) num_even_sets++;
    	}
    	
    	cout << "Number of sets where 4 consecutive random numbers are even: " << num_even_sets << endl;
    	
    	return 0;
    }
    My results:

    The minimum number of "sequences of 4 consecutive even numbers" ever generated was 45, and the max was 88. The mean was 64.
    My Website

    "Circular logic is good because it is."

  5. #20
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> if it didn't...would it be a sign of a bad random number generator?
    Yes. If the odds of it happening are somewhere between 1 in 10^7 and 1 in 10^27 (I believe my calculation and CornedBee's calculation bound the probability), then if it does happen it is a sign of a bad generator. If the odds of it not happening were more like 1 in 3, then you could ascribe it to just chance, but with such great odds it is fairly certain that the number is wrong.

    Also, my 125 to 500 number above was wrong. I had written a program, too, but there was a bug that caused the bad data. I think your results make sense (something that has a 1/16 probability will happen about 62 times out of 997 tries).

    I wonder how many times do you have to run the program before it ever gave a result of 0? And more importantly, if it gave a result of 0 while you were still testing it, you'd probably assume there was a bug.

  6. #21
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    I'm totally at loss why question 2 is meriting such a long debate.
    I don't need to write a piece of code to prove my point (which coincides with DavidP). Please do not think I'm being cocksure. It's just that I trully can't see where the problem is.

    Let's work by elimination:

    Premise:
    It is said the RNG aims at having a uniform distribution

    Step 1.
    Answer (a) the average of the numbers is about 499

    This one is a nobrainer. 499 is at the top of the bell curve. It's an acceptable result. It's in fact an expectable result coming of a uniform distribution RNG. Option a is not and cannot be a part of the answer. So this eliminates answer a and e.

    Step 2.
    Answer (b) each number appears exactly once

    I cannot even start to fathom the odds for this to happen. They are huge. About the amount of starts on our galaxy? Help me with the math please:

    What are the odds of a 6 sided dice throwing all possible numbers on 6 throws?
    The first time we throw it's doesn't matter what number we get: 6/6
    The second time one of the numbers was exhausted: 5/6
    The third time we already can only throw 4 numbers: 4/6
    And so forth: 3/6, 2/6 and finally the last throw there's only one number we can throw: 1/6

    So the odds are: 6/6 * (5/6) * (4/6) * (3/6) * (2/6) * (1/6) = 0.015

    Now do that for a dice with 1000 sides!

    So b has to be the answer or part of the answer.

    Step 3.
    Answer (c) no four consecutive numbers are all even

    Quote:
    You're right, it almost certainly should have sequences of 4 even numbers.


    But...if it didn't...would it be a sign of a bad random number generator? I guess that's the question we have to ask ourselves.
    This is my point of contention.

    My interest for CornedBee calculation was raised here:
    "Likelihood of four numbers containing at least one odd number: 15/16". And I'm not sure why the decision was made to then count the number of 4 number sequences in 1000 numbers. I think that alone demonstrates that c is not a correct answer. Which also eliminates d.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  7. #22
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Could you clarify what you're saying Mario? The answer is d, because both b and c are correct. I'm not sure if you're disagreeing, or if we're just confused by the double and triple negatives.

  8. #23
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    I'm arguing the answer is b.

    (c) can't be correct. It states "no four consecutive numbers are all even". And yet, it was confirmed the likelihood of four numbers containing at least one odd number is 15/16. That's ~93% chance an odd number will show up in a sequence of 4 numbers.

    Next we get to the problem of how to calculate 4 number sequences. And I think we are accepting the "naive" approach too easily. It can't be correct because we are overlapping numbers and their odds.

    Let's get back to a smaller numbers: The dice.
    How many combinations of two numbers exist on 6 throws? 5. What's the odds of an odd number to show on 1 pair of numbers? 1/2. According to the "naive" approach this would mean 1/2^5 = 0.03. That's the odds of getting at least an odd number on every sequence of 2 throws after throwing the dice 6 times. That can't be correct. We know the odds of an odd number are 1/2.

    Instead, I argue all we need is to calculate the odds of an odd number to show in one pair of throws. That calculation is unbounded. We do not need to look at the total of throws. The odds will remain the same.

    Going back to the 1000 numbers and 1000 throws, what's the odds of an odd number to show in a sequence of 4 numbers? 15/16. And that's all we need to know. The odds aren't going to change because we throw 997 sequences of 4 numbers. The 15/16 calculation is the unbounded event. And all we need to know to reach the conclusion 93% chance of an odd number to show in a sequence of 4 numbers is a likely event. Thus this eliminates c.


    EDIT:

    Just for curiosity sake, help me if I'm getting this wrong:
    The odds for (b) I think are calculated as follows (using my dice example on the previous post):

    1000! / 1000^1000 = 4.023e-433
    The odds I believe are "bigger" than the number of stars in the universe
    Last edited by Mario F.; 11-09-2009 at 07:33 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #24
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    I think you're misunderstanding c.

    The question isn't whether there exist four even numbers in a single arbitrary sequence of four numbers. The question is whether there is exist four even numbers in any sequence of four numbers. So you're right that if you arbitrarily picked four consecutively generated numbers, there's a 93% chance that one will be odd, but that's not what the question is asking. It's asking you to go through the entire list of 1000 generated numbers and see if there are any groups of four consecutive even numbers.

    It's not the most straightforward question, and even if you understand what it's asking the answer isn't exactly intuitive. Perhaps that explains why it's such a long debate.

  10. #25
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    Yup. I'm seeing your point.
    Of course! You are right. I'm misunderstanding it.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  11. #26
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    And to prove your point I did resort to some code.

    Only, since I'm teaching myself C#, I should stick to it...
    Apologies not given

    Code:
    static void Main()
    {
        Console.WriteLine("x = 1000 throws before no four consecutive numbers are all even");
        Console.WriteLine("Started at: {0} ", DateTime.Now);
    
        Random r = new Random();
        int num;
        byte nEvens = 0;
        long x = 0; // int64
    
        while(true)
        {
            x++;
            nEvens = 0;
    
            if(x % 1000000 == 0) // report every million sequences of 1000 throws
                Console.WriteLine("=> Still working at x = {0} => {1}", x, DateTime.Now);
    
            int i = 0;
            for(; i < 1000; i++)
            {
                num = r.Next(1, 1001); // [min, max[
    
                if(num % 2 == 0 && ++nEvens == 4) // short-circuit eval.
                    break; // a sequence of 4 even numbers.
                else
                {
                    if(num % 2 != 0)
                        nEvens = 0; // it's an odd. Reset.
                }
            }
    
            if(i == 1000)
                break; // no sequence of 4 even numbers!
        }
    
        Console.WriteLine("x = {0}", x);
        Console.WriteLine("Ended at: {0} ", DateTime.Now);
    
        Console.ReadLine();
    }
    Output until I ^C

    x = 1000 throws before no four consecutive numbers are all even
    Started at: 10-11-2009 04:07:40
    => Still working at x = 1000000 => 10-11-2009 04:07:42
    => Still working at x = 2000000 => 10-11-2009 04:07:45
    => Still working at x = 3000000 => 10-11-2009 04:07:47
    => Still working at x = 4000000 => 10-11-2009 04:07:50
    => Still working at x = 5000000 => 10-11-2009 04:07:52
    => Still working at x = 6000000 => 10-11-2009 04:07:55
    => Still working at x = 7000000 => 10-11-2009 04:07:57
    => Still working at x = 8000000 => 10-11-2009 04:07:59
    => Still working at x = 9000000 => 10-11-2009 04:08:02
    => Still working at x = 10000000 => 10-11-2009 04:08:04
    => Still working at x = 11000000 => 10-11-2009 04:08:07
    => Still working at x = 12000000 => 10-11-2009 04:08:09
    => Still working at x = 13000000 => 10-11-2009 04:08:11
    => Still working at x = 14000000 => 10-11-2009 04:08:14
    => Still working at x = 15000000 => 10-11-2009 04:08:16
    => Still working at x = 16000000 => 10-11-2009 04:08:19
    => Still working at x = 17000000 => 10-11-2009 04:08:21
    => Still working at x = 18000000 => 10-11-2009 04:08:24
    => Still working at x = 19000000 => 10-11-2009 04:08:26
    EDIT:
    Removed the int[4] array and replaced it by a single int; "num". It was a leftover from a first approach and didn't remove it until now.
    Last edited by Mario F.; 11-10-2009 at 05:59 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  12. #27
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    So here is the real conclusion we have come to: professors really need to word their questions better!
    My Website

    "Circular logic is good because it is."

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Computer Programmer Aptitude Battery Test (CPAB)
    By scotty101 in forum General Discussions
    Replies: 40
    Last Post: 02-22-2010, 10:49 PM
  2. Newbie needs help..
    By xpress urself in forum C++ Programming
    Replies: 3
    Last Post: 07-26-2007, 07:22 PM
  3. A very long list of questions... maybe to long...
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-16-2007, 05:36 AM
  4. My C++ test is COMING!!...
    By [Z-D] in forum C++ Programming
    Replies: 52
    Last Post: 12-01-2006, 07:02 PM
  5. Bitwise Test Questions
    By Mister C in forum C Programming
    Replies: 9
    Last Post: 11-27-2002, 05:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21