CS 215 Homework #2

1. This problem refers to the FastPow algorithm from Problem 3.1 in your text.
   1. What is the running time of this algorithm? (See the choices in Problem 3.1.) Explain why.
   2. Show the steps in computing 3²⁹.
   3. Give some idea of why this algorithm should give us the correct output value. (Doesn't have to be a formal proof, but some explanation of why it makes sense that this would work.)

2. Consider the following "algorithm":^*

   void DC(int n, keytype S[])
   {
     int dummy;
     if (n <= 1)
       return;
     for (int i = 1; i <= 4; i++)
       DC(n/3, S);
     for (int i = 1; i <= n; i++)
       for (int j = 1; j <= n; j++)
         dummy = S[i]+S[j]; //COUNT THIS (Number of array accesses)
   }
   

   Write a recurrence equation that gives the time T(n) taken by this algorithm. Determine the order of growth for T(n).

3. Rework Problem 2 with the constant 4 that appears in the algorithm replaced by 9.^*

4. Rework Problem 2 with the constant 4 that appears in the algorithm replaced by 81.^*

5. Consider the following "algorithm":^*

   void waste(int n, keytype S[])
   {
     for (int i = 1; i <= n; i++)
       for (int j = 1; j <= i; j++)
         print i, j, n;  //COUNT THIS
     if (n > 0)
       for (int i = 1; i <= 4; i++)
         waste(n/2, S);
   }
   

   Write a recurrence equation that gives the time T(n) taken by this algorithm. Determine the order of growth for T(n).

6. (OPTIONAL CHALLENGE) Consider the following "algorithm":

   void waste(int n, keytype S[])
   {
     for (int i = 1; i <= (2 * n); i++)
         print S[i]; //COUNT THIS
     if (n > 1)
       {
         waste(n-1, S);
         waste(n-1, S);
       }
   }
   

   Write a recurrence equation that gives the time T(n) taken by this algorithm. Solve the recurrence equation. NOTE: You cannot use the Master Theorem to get the time complexity for this recurrence. You will need to use a different method to solve this recurrence.