Non-Programming Exercises:

1. Consider the following function that will calculate the product of its two input parameters. (It does with this without using any "multiply", but just with addition and subtraction.)

   
   // mult: inputs X and Y both > 0
   int mult(int X, int Y) {
      int x = X, y = Y, p = 0;
      while (y > 0) {
         p = p + x;
         y = y - 1;
      }
      return p;
   }
       

   1. Try to guess the loop invariant. (I'll give it to you on Tuesday, 26 February 2004.)
   2. Carefully write out the four steps similar to those given in the lecture notes under XI.4 a-d (for exponentiation in the notes).
   3. What goes wrong in the proof if one writes p = 1; in error instead of p = 0;?
   4. What goes wrong in the proof if one writes y = y + 1; in error instead of y = y - 1;?

   ---

2. Consider the following function that will calculate the quotient and remainder of its two input parameters. (It does with this without using an actual "divide", but just with addition and subtraction.)

   The inputs are

   • n >= 0 (the "dividend") and
   • d >= 1 (the "divisor").

   The algorithm calculates and returns

   • q >= 0 (the "quotient") and
   • r (the "remainder"),

   such that

   • r >= 0,
   • r < d, and
   • n = d*q + r.

   Here is the picture:

   
            q
        +-------
     d  |   n
   -----+
          ------
            r
   

   Here is the function:

   
   // div: inputs n >= 0 and d >= 1, returns the pair (q, r)
   (int, int) div(int n, int d) {
      int q = 0, r = n;
      while (r >= d) {
         q = q + 1;
         r = r - d;
      }
      return (q, r);
   }
       

   The loop invariant is:

   
   n = q * d + r
   

   Carefully write out the four steps similar to those given in the lecture notes under XI.4 a-d (for exponentiation in the notes).

   ---

3. This is a question about the extended GCD algorithm on page 15 of GCD (PDF). Recall that the loop invariant consists of the following three equations. (Note that the equals sign is mathematical equals.)

   
   x*u[0] + y*u[1] = u[2]
   x*v[0] + y*v[1] = v[2]
   x*t[0] + y*t[1] = t[2]
   

   This question asks you to prove two parts of using the loop invariant to show that the algorithm works.

   1. Show that the first two equations are true just before the while loop. (This should be very easy, if you are understanding what is wanted.)
   2. Assume the first two equations are true at the beginning of the while loop (after executing the while zero or more times). Assume that the first three assignments inside the while loop are executed:

      
      t[0] = u[0] - v[0]*q;
      t[1] = u[1] - v[1]*q;
      t[2] = u[2] - v[2]*q;
      

      With these newly calculated values of the array t, and assuming the first two loop invariant equations are true, show that the third loop invariant equation is true, that is, show that:

      
      x*t[0] + y*t[1] = t[2]
      

   3. The argument in part b above works no matter what value the variable q has. Explain why q needs to be set to u[2]/v[2] in the algorithm.

4. The Birthday Paradox (text, page 267, problem 5) asks how many people with random birthdays does it take to have better than even odds that at least two have the same birthday (same month and same day). (This is ignoring February 29.)

   It is easier to calculate the probability that among n people, no two have the same birthday. Denote this by N(n). For two people, the second one will have a birthday different from the first with probability:
           N(2) = 364/365.
   If there is a third person the probability that he will have a birthday different from the first two (which are assumed distinct now), is 363/365, so that
           N(3) = (364/365)*(363/365).
   Similarly,
           N(4) = (364/365)*(363/365)*(362/365).
   Of course, N(1) = 1.

   The probability, call it S(n), that at least two people from among n have the same birthday is just:
           S(n) = 1 - N(n).

   Write a simple program that will calculate and print S(n) for n = 1, 2, 3, ..., 50. These should be calculated as doubles.

   ---

5. What does the previous exercise say about inserting into a hash table of size 365?