Lotteries- choose your own numbers or buy a quickpick?

Problem:  Is it better to choose your own lucky numbers or buy a quick pick ticket?  Does it matter?  (Thank you to Wayne L. for this question)


Solution:  The first and obvious answer is that it doesn't matter!  Assuming that the drawing is fair (and it's always good to list assumptions) - then pick whatever numbers you want


This seems like a reasonable answer.  But, now let's challenge the assumptions and see exactly what we're optimizing for before declaring victory.


Ok, so first, we assume that the lottery is fair. That is to say that a truly random set of numbers is drawn.  We assume that some numbers are not more common than others due to the weighting of the paint on a ping pong ball, or simply a not entirely accurate random number generator, whatever process happens to be used.


Let's say that this is true, that we are not going after the random number generator.  So, this assumption seems to hold.


Are there any other assumptions?

Well, let's try a simple example.  Assume that we have a simple lottery of the numbers 1-10.  What would you choose?


7?


Well, what would most people choose?  


You're probably aware that humans are very bad at picking random numbers.  When asked to pick random numbers between 1-10, there is not an even distribution, but many people choose 2 and 7.


So, let's say you chose 7, is this good or bad?


Now, two things can happen.  One, you can lose, in which case it didn't really matter. Or, you can win -- which seems good.


But, as 7 is very common, someone else, or many people likely chose 7.  So, you'll end up splitting the winning with them.


Here's seems to another optimization, that you want to choose a number that no one else does, so if you win, your expected winnings are higher.


And, this assumption, strongly gives an answer to the original question.  Since humans are bad at choosing random strings, you're more likely to have others choosing the same set of numbers if you choose, than if you get a quick pick.  And, since the likelihood of winning doesn't change, but the expected amount does, quickpicks are the way to go if you're optimizing for expected value!


/* Please let me know if you find bugs or alternative solutions.  Thx, Noah */

Next Fibonacci number (non-recursive)

Problem:  Write a non-recursive function to prints the xth Fibonacci number which can do it in linear time


int finNum(int num) {...}


Solution:  The last two problems go into the Fibonacci sequence, so let's start by thinking about how this could be implemented non recursively.


We would need to iterate and always keep track of the two previous numbers, and then finish up with the new Fibonacci number.  And, if we pay attention to error cases, this should be straight forward.


The iteration step needs to be done in the correct order and can be a little tricky, so you may want to write out an example, say 4, and then try it.


So, let's go ahead and implement this:


int fibNum(int num) {

  int i, fib, fib0, fib1;

  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;


  /* Now, write an iterative loop to figure out the fib num */
  /* Intialize fib0 as 0, fib1 as 1, and fib as their sum (1) */
  for (i = 2, fib0=0, fib1=1, fib=1; i < num; i++) {
    fib0 = fib1 + fib;
    fib1 = fib;
    fib = fib0 + fib1;
  }
  
  return fib;
}


Well, that's it.  What's the run time?  Since we go through the lop up to num-2 times, it is num.  We should check boundary cases of num = 2, and an error.  


Also, let's test with the number 5 -- and it works.


So, we have now implemented a non-recursive solution.  Let's talk about the trade-offs.  First, it's longer than the simple fib implementation.  But, it is efficient (linear) and does not have the recursive overhead.


The boundary cases can be tricky, and it doesn't read as nicely as the simple recursive Fibonacci solutions.


This is a problem that seems really easy, but it's important to always check the boundary cases and do an example, as trying to figure out all the fib0, fib1 and fib otherswise and where to initialize the variables, is very tricky otherwise, but fairly simple with an example.


/* Please let me know if you find any bugs or other solutions. */

Fibonacci (today) + Fibonacci (yesterday)

Problem:  Write a recursive function to prints the xth Fibonacci number which can do it in linear time


int finNum(int num) {...}


Solution:  


Yesterday, we printed the the nth Fibonacci number with a very simple algorithm, but wow, was it slow.  The running time was O(2^n).  Wow.  That's really, really bad, even for relatively low values of n (like 60).


Well, we have to keep it recursive, but need to do in linear time.  


Let's start by taking a look at yesterday's code:




int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibNum(num-1) + fibNum(num-2));
}


This code makes spawns to new calls, which each spawns two more threads as it recurs on itself.  This leads to the really horrible run time for the code.  Clearly, we have to do better


Also, this is very, very repetitive, as we continually call fibNum on the same number.  For example, in yesterday's example, we would call fibNum on fibNum of 1 or 2 as much as O(2^n).  Other numbers are called significantly too.  This seems unnecessary


Think about how you could change the number of times that fibNum is called for each number.  


One solution might appear to build a data structure, that you would populate the first time you get a fibNum, then could check if you had already called fibNum on that number, and recur if you did not.  This would certainly work.  You could do this by storing an array, which would allow easy lookup by index, and then only recur if it was undefined.


Good solution, but we can do even better, without additional memory.


To provide a hint, take a look at the return statement.  The Fibonacci function requires the two previous values, but we do not keep track of them, so we have to recur each time to get them.  Think about a recursive function which kept track of the two previous values each time.


In fact, if we could do this, we would not have to go ahead and spawn two threads each time.  To do this recursively, we would need a function which kept track of the two previous values, and then would update on each recursive call, so that it would 'shift' and move the previous value back two, and our current value back one.  


The base case here would be reaching the second value, or num.  And we can imagine num getting smaller until we reach the base case, while we build up the value for num.


This is a slightly more complicated function, but much more efficient.  It is a recursive solution that keeps track of the two previous values each time, and we seed a helper funciton with the first two values, 0 and 1.


Now, using this recursive insight, we can go ahead and code the problem, making sure that check bases cases.



int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibHelper(num, 0, 1);
}





int fibHelper(int num, int one_prev, int two_prev) {


  if(n == 1) return two_prev;
  return fibHelper(n - 1, two_prev, one_prev  + two_prev);
}




Now, let's try an example, say 5.  Yup.  It works!


So, what is the run time of this function?  We will make the same number of calls to fibHelper as num, so it is O(n), a WHOLE lot faster that the previous, simple implementation.  


We can also drop one of the base cases now, for simplicity, as we don't need to treat num=2 as a special case anymore, which give us (fibHelper remains the same):



int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;


  /* and now, recursive call to figure out the number */
  else return (fibHelper(num, 0, 1);
}





This is a good example of where by simply going a little further, we are able to take a disastrously inefficient function, and make it better, and why you shouldn't stop at just a 'good' solution.


/* Please let me know if you find any bugs here.  */

The Fibonacci Sequence

Problem:  Write a recursive function to prints the xth Fibonacci number.


int finNum(int num) {...}


Solution:  


This is a canonical recursive problem, but can be encountered.  Let's start this problem with a review of the Fibonacci sequence.  This is a sequence of numbers where each number is the sum of the previous two numbers, and the first two numbers in the sequence are 0 and 1.  


A mathematician expresses this as:






Now, let's do an example of the first say, 7, Fibonacci numbers to make sure that we get the pattern:


0
1
1
2
3
5
8


And we could go more.  


Well, with this, it seems set up for recursion.  We have our two base cases, which is if the num is 1 or 2.  And, otherwise, we have the sum of the two previous numbers.


With this, we can code it up, and we need to check for base cases:


int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibNum(num-1) + fibNum(num-2));
}


And, that's it.  Let's do an example, say 7 above, and walk through it to make sure that it works.


It does!


So, this solution works recursively.  What is it's runtime?


Well, it calls fibNum two times more as num grows.  This means that the function is O(2^n).  This is horrible for even small sizes of n.  Wow.  Just awful!


Think about how to make this better, while still recurring.  That's tomorrow's problem. 


/* Please let me know if you find any bugs here.  */