Assignment 10

Harvey Mudd College
Computer Science 60
Assignment 10, Due Friday, April 19, by midnight

Algorithmic Complexity: Sorting it all out...

Problem 1: Finding running times (10 pts.)

This problem asks you to find the big-O running time that arises from the following two recurrence relations and one set of nested loops. You may write your answers or type them into a file named bigO.txt.

(A) (3 points)

What is the big-O running time (in terms of N) of a recursive program that gives rise to the following recurrence relation. You may assume the input size, N, is even, and T(0) = 0.

  T(N) = 2N + T(N-2)

(B) (3 points)

What is the big-O running time (in terms of N) of a recursive program that gives rise to the following recurrence relation. You may assume the input size, N is a power of 2, and T(1) = 0.

  T(N) = 2 + 4T(N/2)

(C) (4 points)

What is the big-O running time (in terms of N) of the following set of nested loops: You may assume the input size, N, is a power of 2. Only one (counted) operation is in the inner loop.

   for (int i=N ; i>=1 ; i=i/2)
   {
     for (int j=i ; j>=1 ; j=j/2)
     {
       // 1 operation is counted here
     }
   }

Submitting these problems

You may submit this through cs60submit by typing your answers into a file named bigO.txt and the running it the usual way, i.e.

  cs60submit bigO.txt

Alternatively, you may write out the answers and hand them in under the door of Olin 1265 by midnight on Sunday.

Problem 2: The Heap data structure (30 points)

This problem asks you to write a Heap class in Java (in a file named Heap.java). This is equivalent to writing a sorting routine, since Heaps can be used to sort lists efficiently -- in time O(n*log(n)). A starter file with toString in it is at /cs/cs60/as/a10/Heap.java.

You won't need to include an explicit sorting routine, but you will need to have the following data and methods in your class:

DATA MEMBERS
- int[] A
  
  This is the only data member you will need in your Heap class. As discussed in lecture, you should use A[0] to store the number of elements of A currently used for the heap. The actual elements on the heap will all be ints and will be indexed from 1 to A[0], inclusive.
METHODS
- public String toString()
  
  Do not write this method! In order to be able to test your heap class for sorting (and other uses), you will need to use the toString provided in /cs/cs60/as/a10/Heap.java.
- public Heap(int capacity)
  
  The Heap constructor takes one argument -- the maximum capacity of the heap. Keep in mind that since the values in the Heap are indexed starting from 1, you'll need to take that offset into account when allocating the data member array (A).
- public boolean isEmpty()
  
  This method should return true if the no elements are being stored in the heap, and false otherwise.
- public boolean isFull()
  
  This method should return true if the number of elements stored is equal to the heap's capacity, and false otherwise.
- public void addElement(int e)
  
  This method should add the integer e to the invoking heap if there is room; otherwise it should print a warning message and not add e. Remember that you need to preserve the heap property that each node is larger than both of its children. We will discuss the algorithm for maintaining this property in class, but as a reminder, it involves placing e at the last position in the heap and then "percolating it upward" as far as it will go.
- public int extractMax()
  
  This method should return the largest element in the invoking heap (unless it's empty, in which case, it should print a warning message and quit). Again, the heap property needs to be preserved; we will go over the technique in class -- it involves moving the last element in the heap to the first position and then "percolating it downward" as far as it will go.

Testing your Heap class

As with previous Java classes, there are a number of tests in /cs/cs60/as/a10, named Test#.java. You can copy those to your directory (with your Heap.java file), compile them with

  javac Test#.java

and then run them with

  java Test#

The expected outputs are in /cs/cs60/as/a10/Test#.out; you might compare them by eye or with the diff command:

  java Test# | diff - Test#.out

What about sorting?

The tests listed above will use your Heap data structure to sort various lists of elements. The advantage of a heap is that new elements can be added and organized at any time, so that the resulting set of values is still very quickly sorted.

Problem 3: Power Computing! (10 points)

This problem asks you to measure the empirical running time of four different methods for finding powers and compare these real times with their expected big-O running times. Different ways of computing powers?

We will examine four methods for finding powers of some integer base (b). The running time of each will be expressed in terms of the size of the exponent, i.e., the power, N. For simplicity, we will always use the same base, 7 and we will always use values of the power, N that are 2^i for some i. That is, the powers will themselves be powers of 2!

The algorithms we are going to contrast are the straightforward ("regular") power-computing algorithm:

       static double regDoublePower(int b, long N)
       {
         double base = b;
         double result = 1.0;
     
         while (N > 0)
         {
           result = result * base;
           --N;
         }
     
         return result;
       }

with a power-computing algorithm called the "Russian Peasant's" (rp) method:

       static double rpDoublePower(int b, long N)
       {
         double sq = b;
         double result = 1.0;
     
         while (N > 0)
         {
           if (N%2 == 1) result = result * sq;
           N = N/2;
           sq = sq * sq;
         }
         return result;
       }

Further, these two methods use doubles; they will also be compared to the same methods using exact arithmetic with Java's BigInteger class. First, the ordinary method for computing powers -- this time with BigInts:

       static BigInteger regBigIntPower(int b, long N)
       {
         BigInteger base = new BigInteger(""+b);
         BigInteger result = new BigInteger("1");
     
         while (N > 0)
         {
           result = result.multiply(base);
           --N;
         }
     
         return result;
       }

and, second, the Russian Peasant's version with BigInteger:

       static BigInteger rpBigIntPower(int b, long N)
       {
         BigInteger sq = new BigInteger(""+b);
         BigInteger result = new BigInteger("1");
     
         while (N > 0)
         {
           if (N%2 == 1) result = result.multiply(sq);
           N = N/2;
           sq = sq.multiply(sq);
         }
         return result;
       }

What to do

Analyze the two basic algorithms (regular and Russian Peasant's method) and find their big-O running time in terms of N (the power to which the base is raised). Consider one multiplication to be one step. Place your answers in a comment at the top of your Power.java file.

The file /cs/cs60/as/a10/Power.java already contains these four methods. It also contains a main method that creates a table of running times for the regDoublePower method. Here is what I obtained (it will differ slightly from run to run):

regDoublePower
  power: N            T/1         T/logN            T/N          T/N^2          T/N^3
        16     +0.000E+00     +0.000E+00     +0.000E+00     +0.000E+00     +0.000E+00
        32     +1.000E+00     +2.885E-01     +3.125E-02     +9.766E-04     +3.052E-05
        64     +0.000E+00     +0.000E+00     +0.000E+00     +0.000E+00     +0.000E+00
       128     +1.000E+00     +2.061E-01     +7.812E-03     +6.104E-05     +4.768E-07
       256     +2.000E+00     +3.607E-01     +7.812E-03     +3.052E-05     +1.192E-07
       512     +3.000E+00     +4.809E-01     +5.859E-03     +1.144E-05     +2.235E-08
      1024     +7.000E+00     +1.010E+00     +6.836E-03     +6.676E-06     +6.519E-09
      2048     +1.300E+01     +1.705E+00     +6.348E-03     +3.099E-06     +1.513E-09
      4096     +3.100E+01     +3.727E+00     +7.568E-03     +1.848E-06     +4.511E-10
      8192     +5.800E+01     +6.437E+00     +7.080E-03     +8.643E-07     +1.055E-10
     16384     +1.170E+02     +1.206E+01     +7.141E-03     +4.359E-07     +2.660E-11
     32768     +2.560E+02     +2.462E+01     +7.812E-03     +2.384E-07     +7.276E-12
     65536     +4.730E+02     +4.265E+01     +7.217E-03     +1.101E-07     +1.680E-12
    131072     +9.750E+02     +8.274E+01     +7.439E-03     +5.675E-08     +4.330E-13
    262144     +1.936E+03     +1.552E+02     +7.385E-03     +2.817E-08     +1.075E-13
    524288     +3.876E+03     +2.943E+02     +7.393E-03     +1.410E-08     +2.690E-14

You will need to alter the code in that file to expand this table to include runs of all four algorithms. Let the table grow large enough to get a sense of the patterns emerging. Also, you may add columns to the table to investigate other big-O running times, if you wish.

Write an analysis (about a paragraph) describing how well the empirical evidence supports the big-O running times you found in step (1). Consider any differences between the double and the BigInteger versions in this analysis.

What to hand in

Submit your Power.java file in the usual way. Include in a large comment at the top the table of running times that you generated, your big-O analysis, and your analysis of how well the table and big-O estimates agree.

Submitting

You should submit your Power.java (from #3) and Heap.java (from #2) in the usual way, i.e., with

% cs60submit Power.java
% cs60submit Heap.java

You can also submit your typed bigO.txt file (from Problem 1) in the same way, i.e.,

% cs60submit bigO.txt

or by writing out your answers and putting them under the door of Olin 1265 by midnight Sunday.

Reading

Complexity and its analysis is covered in Chapter 11 of the text. Also, most (hopefully all) of the material needed for these problems will be covered in class.

Extra Credit

For optional bonus credit (up to 20%), consider the following "Totally Excellent" (?) Sorting Algorithm, Stoogesort, proposed by Professors Curly, Mo, and Larry of the Pasadena Institute of Technology and conveyed to our own Prof. Hadas at a recent algorithms conference.

If the list is two elements long, compare the two elements and swap them if necessary.
If the list is more than two elements long, use recursion to sort the first two-thirds of the elements in the array. (Suppose the sorting is in-place, i.e., the elements get rearranged, rather than creating a new array.)
Then, use recursion again to sort the last two thirds of the array.
Finally, use recursion a third time to sort the first two thirds again.

Things to do:

Argue briefly (a couple of sentences) why this algorithm actually does sort the input list.

Write down the recurrence relation for the running time of Stoogesort.

Solve this recurrence relation using the unwinding technique. Carefully show all the steps in your unwinding analysis. You may assume that N (the length of the array to be sorted) is a power of 3/2. (Admittedly, there are very few powers of 3/2 that are integers, but the idea is that you can assume you'll always be able to split the list into thirds, until you get down to lists of size 2, which are the base case.)

Express the running time of Stoogesort as O(n^x) where x is some real number. Give the actual value of x.

How does the running time of this algorithm compare to that of Mergesort or Quicksort or Heapsort? Is it better or worse? Explain your answer carefully.

Type your answer to this question in a file named stoogesort.txt and submit with cs60submit or or write them on a piece of paper and hand it in under the door of Olin 1265.

Harvey Mudd College Computer Science 60 Assignment 10, Due Friday, April 19, by midnight