CPSC 225, Spring 2009
Analysis of Algorithms Assignment

This assignment is
due on Friday,
February 6.

Exercise 1: Suppose that A and B are n×n matrices. (That is, they are two dimensional arrays that have n rows and n columns.) The matrix product of A and B is the array computed by the following subroutine:

         /**
          * Compute and return the matrix product of two n-by-n matrices.
          */
         static double[][] matrixProduct( double[][] A, double[][] B, int n ) {
             double[][] C = new double[n][n];
             for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    double t = 0;
                    for (int k = 0; k < n; k++)
                       t = t + A[i][k] * B[k][j];
                    C[i][j] = t;
                }
             }
         }

Analyze the run time of this algorithm in terms of n. That is, find a simple function f(n) such that the run time for matrices of size n is Θ(f(n)). Explain your reasoning.


Exercise 2: Let A be an array of n numbers (of type double). Let T be another array of size n. Suppose that we want to compute "cumulative totals" for A and store them in T. That is, we want T[i] to be

            T[i]  =  A[0] + A[1] + . . . + A[i]

for i = 0, 1, 2, ..., n. Here are two different algorithms for doing this computation. Analyze the run time for the two algorithms and compare them. Explain your reasoning. (To analyze an algorithm, you should try to find a simple function f(n) such that the run time for a problem of size n is Θ(f(n)).)

         Algorithm 1:                               Algorithm 2:
         
            for (int i = 0; i < n; i++) {              T[0] = A[0];
               double total = 0;                       for (int i = 1; i < n; i++) {
               for (int j = 0; j < i; j++)                  T[i] = T[i-1] + A[i];
                  total = total + A[i];                }
               T[i] = total;
            }

Exercise 3: The analysis of an algorithm often depends on how the input size is measured. Consider the following algorithm, which computes an output integer based on the value of an input integer, n:

           /**
            *  Considering n as a binary number, count the number of bits in n
            *  that number that are equal to 1.
            */
           int countSetBits(int n) {
               int bitCt = 0;
               while (n > 0) {
                  if (n % 2 == 1)
                     bitCt++;
                  n = n / 2; // integer division!
               }
               return bitCt;
           }

Give an analysis of the run time of this algorithm in terms of n. That is, find a function f(n) such that the run time is Θ(f(n)) for input n.

Now, note the fact that this method is actually manipulating bits, so maybe a better measure of the input size would be the number of bits (zero and one) in n. Let d be the number of bits in n. Give an analysis of the run time that uses d as a measure of the input size. (That is, express the run time as Θ(g(d)), for some function g(d), instead of Θ(f(n)).) Explain your reasoning.


Exercise 4: Give an analysis of algorithms for the following (rather useless) code segment. Analyze the run time, using the length, n, of the array as a measure of the input size. Explain your reasoning.

         int n = A.length;  // A is an array of ints of length n.
         int k = 2;
         while (k < n) {
            int t = 0;
            for (int i = 0; i < n; i++) {
               t = t + A[i];
               if (t % k == 0 || i == n-1) {
                   System.out.print(t + " ");
                   t = 0;
               }
               System.out.println();
            }
            k = 2*k;
         }

Exercise 5: The obvious algorithm for finding the maximum in an array of length n clearly has run time Θ(n). Consider the following funny recursive algorithm for doing the same thing:

         /**
          *  Returns the largest number among A[low], A[low+1], ...
          *  A[high].  Note that high must be >= low.  To find the
          *  maximum of the entire array, call recursive_max(A, 0, A.length-1).
          */
         int recursive_max( int[] A, int low, int high ) {
             if (high == low)
                 return A[low];  // There is only one item to consider; it's the max
             else {
                 int mid = (low + high) / 2;  // Note: mid >= low and mid < high
                 int m1 = recursive_max(A, low, mid);     // max of first half
                 int m2 = recursive_max(A, mid+1, high);  // max of second half
                 if (m2 > m1)  // overall max is bigger of max's of the two halves
                    return m2;
                 else
                    return m1;
             }
         }

Give a run-time analysis of this algorithm. How does its run time compare to the run time of the usual algorithm for finding the maximum value in A? Explain your reasoning. (This is a tough question, and your answer will have to be pretty informal. Try to figure out how the algorithm works. Try working it through when the length of the array is 8. This algorithm might not make much sense to you until after we have covered QuickSort.)