Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343/3341
 Analysis of Algorithms
 Fall 2012
 Recitation 4
 Quicksort, Exp, etc. 
    Week 4: Sep 18-20
 Due (on time): 2012-09-24  23:59:59
 Due (late):        2012-09-28  23:59:59

Recitation 3 should be submitted following directions at: submissions with deadlines
  • 2012-09-24  23:59:59 (that's Mon, 24 Sep 2012, 11:59:59 pm) for full credit.
  • 2012-09-28  23:59:59 (that's Fri, 28 Sep 2012, 11:59:59 pm) for 75% credit.

  1. The first problem will be made accessible during the Recitation hour: Rec 4, In-Class Problem 1 (password protected, use "CS3343" without quotes for "User Name" and password from class just before the recitation).

  1. The pow(x, y) function calculates xy. Implement pow using just the log and exp functions in Java or C. [Both these functions are base e. The logs page would be helpful.]

  1. Consider the "Modular-Exponentiation" algorithm in your textbook page 957, shown in the image below. The algorithm has several features not relevant to this discussion: Since it is a part of the RSA cryptosystem implementation, there is an extra parameter n, and at each stage, the algorithm takes the remainder on division by n. The variable c is used only for a proof of correctness. Eliminating n and c, and changing it to the C language, we get the function on the left below. The original algorithm from class is given at the right below.

    // expon: calculates a^b, where
// b = b[k] b[k-1] ... b[0] (binary)
// Rewritten from your text.
int expon(int a, int b[], int k) {
   int d = 1; // final result
   int i;
   for (i = k; i >= 0; i--) {
      d = d * d;
      if (b[i] == 1) d = d * a;
   }
   return d;
}
    		 
    // expon: fast exponentiation
// presented in class
int expon(int a, int b) {
   int d = 1; // final result
   while(b > 0) {
      if (b%2 == 1) d = d*a;
      b = b/2;
      if (b > 0) a = a*a;
   }
   return d;
}

    Convince yourself that these algorithms are different by tracing through the execution of each one, using the inputs a = 3, and b = 22 = 101102. [Be sure to keep the two separate. For each loop execution, show the results of the two assignments (one only conditionally executed). Be careful, because b on the left is an array, but an int on the right. If you like, you can show the results as powers of 3. The final answer in each case is 322 = 31 381 059 609.]

  1. The following is a recursive definition of ab for integers a and a. (This example is due to A. Levitin, from his algorithms text.)

    1. Implement this definition in Java or C using recursion. [Just follow the definition. I used an extra function int sqr(int r){ return r*r; }, since Java and C don't have a squaring or exponentiation operator. (Why not? Couldn't they use ^ for this, or ** like Fortran?).]

    2. Use your program to calculate 319 and 513.

    3. This program does essentially the same calculations as one of the two earlier methods above. Which one do you think? [Don't just guess or spend a lot of time on this.]

  1. This problem deals with the Fake Coin Weird Topic.

    1. What about n not an exact power of 3? Say in detail how you would handle this.

    2. We improved from log2(n) steps to log3(n). By what factor did the number of steps improve?

    3. Suppose we don't know whether the fake coin is heavier or lighter. Can you handle this case efficiently? (One or a few extra weighings.) (And, hey, not just a "Yes" or "No" answer!)

Revision date: 2012-09-17. (Please use ISO 8601, the International Standard.)