CS 241, Spring 99, Expected Value Practice Excercises

As requested, here are some more practice excercises on expected value computations. We can go over these problems in the help session or if you want to send your solution to sg@cs we can check it for you. Also, of course you can ask for help with these problems during our office hours.

1. Consider the problem of searching for x in an array A of n elements. with the following procedure:

   boolean search(n,A,x){   \\searches for x in the unsorted array A[0..n-1]
      int i=0;
      while (i <= n-1 && A[i] != x)   \\searches for x
         i++;
      if (A[i] == x){                 \\if found
         return true;
       }
      else return false;
   

   In each of the following problems you are to give an exact answer for the number of times that A[i] != x is executed.
   1. Assume that with probability 1/2, x is not in A and with probality 1/(2n) x is position i of the list for i = 0,1,...,n-1.

      solution

   2. Assume that for 0 <= i <= n-1, that the probability that x is in position i of the array is 1/(2^{i+1}) and with probability 1/(2^n) that x is not in the array.

      solution

   3. Assume that with probability 1/2, x is in A[0], with probability 1/4, x is in A[1] and with probability 1/4, x is not in A.

      solution