Homework 4 Solutions

I solved these problems by first assuming that I was working with an algorithm of the specified form (linear, O(nlog(n)), etc) and then taking t=0.5ms for n=100 as a data point gathered from a run of that algorithm. From there it is pretty much plug-and-chug to find the n for the other data point (with t=60).

0.5ms = 0.5e-3 s = 5e-4 s
t = cn
5e-4 = c(100)
c = 5e-6

t = cn
60 = (5e-6)n
n = 1.2e7

t = cnlog(n)
5e-4 = c(100)(log(100))
5e-4 = 200c
c = 2.5e-6

60 = (2.5e-6)nlog(n)
nlog(n) = 2.4e7
Guess and check shows that n = ~3.75e6

1. O(n)
2. n/2 = O(n)
3. O(n^2)
4. 2n = O(n)
5. n * n^2 = n^3 = O(n^3)
6. 1 + 2 + ... + (n-1) + n = n^2/2 = O(n^2)
7. n * (1 + 2 + ... + n^2) = n * (n^4/2) = O(n^5)
8. log_2(n) = O(log(n))

This problem is not required for the homework (there was some confusion between different versions of the book).

Part A - Suppose we check N for primality by trying to divide it by all numbers from 1 to N and seeing if there is a remainder. This will have a running time of O(N).
Part B - With B bits, we can represented 2^B different values. Therefore, in terms of N, B = log_2(N).
Part C - The worst case running time will be O(2^B). This makes sense, considering we previously determined that the worst case running time was O(N) and 2^B bits to represent N.
Part D - It will take 2^40 / 2^20 = 2^(40-20) = 2^20 times as long to factor the 40 bit number as it will to factor the 20 bit number. This is a great example of the disparity between the size of a prime number (as used in cryptography) and the amount of time it takes to factor it; Here the 40 bit number only consumes twice as much space as the 20 bit number, but requires 2^20 = ~1 million times as long to factor.

Assuming the implementation of Insertion sort being used is fairly intelligent (in that it will only move the element that was just added to the sorted sub array if necessary), then the running time for 8.4 and 8.5 will be linear (O(n)).

For example, let's look at the array [5, 5, 5, 5] for 8.4. The algorithm should begin with index 0 as the only member in the "current sorted sub array". It will then add the number at index 1. Seeing that no moves are necessary to keep the sub array (from index 0 to 1) sorted, it will add the number at index 2, and then 3. This clearly has linear running time. Something similar should happen for an already-sorted array for problem 8.5

For problem 8.6, the running time will be O(n^2). In this case, each element added to the sorted sub array will have to be shifted through all of the elements currently in that sub array. Try a sample run if you are still unclear on this.

When analyzing Shell sort, keep in mind that it is actually Insertion sort that does all of the sorting / moving of elements. Therefore, it is often helpful to understand how Insertion sort behaves with the given input, and then see what affect Shell sort has on that.

As we just saw in part B, the running time of Insertion sort with an array with all the same values (8.4) and an already-sorted array (8.5) will be O(n). So, what affect does the varying gapSize introduced by Shell sort have on all of this? Well, for each iteration of Shell sort, the cost is O(n). Assuming we use the most efficient version of Shell sort (which uses a gapSize from array.length / 2 to 1, dividing by 2.2 at each iteration), there will be log_2.2(n) (that's log base 2.2 of n) iterations. Therefore, the cost will be log_2.2(n) * n = O(nlog(n)). The bottom line here is that Insertion sort has to, at least, look at each element once (meaning a run time of O(n)) and the outer loop (the Shell sort gapSize iteration loop) must run log(n) times, leading to a run time of O(nlog(n)).

Let's now look at the running time of Shell sort with a reverse sorted array as input (8.6). For a given gapSize, there will be gapSize sub arrays, each of length n/gapSize. We know that Insertion sort requires O(m^2) to sort a reverse-sorted array of length m. Here, m will be (n/gapSize) for each sub array. This means that one sub array will cost (n/gapSize)^2 to sort. There are gapSize sub arrays, so the total cost will be gapSize * (n/gapSize)^2 = n^2/gapSize. Now, that is the cost just for a single gapSize. Assuming we have gapSize's from n/2 to 1, stepping by a factor of ~2 (as with the most efficient version of Shell sort), the sum of all of the iterations will be n^2/(n/2) + n^2/(n/4) + n^2/(n/8) + ... + n^2/2 + n^2/1 = 2n + 4n + ... + n^2/2 + n^2/1. If we factor out an n, we get n(2 + 4 + ... + n/2 + n). We know that the inner portion, which is the sum of factors of 2 from 2 to n, is approximately equal to 2n. Therefore, the total cost is n(2n) = 2n^2 = O(n^2).

The problem with the above analysis is that it doesn't take into account the benefits provided by earlier sorts (with larger gapSize's) passed down to later sorts (with smaller gapSize's). This is precisely what makes Shell sort efficient (in that the final iteration, with gapSize=1, should be sorting a nearly sorted array), and what makes it hard to analyze. Let's just say that the above is an absolute worst case analysis and that the actual running time will likely be much faster.

For input of a given size, Merge sort always runs in O(nlog(n)). In fact, it always requires exactly the same number of operations.

Assuming we use some intelligent method to choose the pivot (such as always choosing the middle element (that is, the element at index n/2) or using the median-of-three technique, both described in the book) and stopping on elements equal to the pivot (also described in the book), the running time for all three inputs will be O(nlog(n)).

The last case (with reverse sorted input) is worth examining in further depth. Suppose we have input [9, 8, 7, 6, 5, 4, 3, 2, 1]. 5 will be the pivot in this case, whether we use the n/2 element or use the median-of-three technique. After swapping the pivot to the end, the array will be: [9, 8, 7, 6, 1, 4, 3, 2, 5]. After partitioning, the array will be: [2, 3, 4, 1, 6, 7, 8, 9, 5]. After reinstating the pivot, and just before making recursive calls to quicksort, the array will be: [2, 3, 4, 1, 5, 7, 8, 9, 6]. A few anamolies aside, this is a nearly sorted array. As such, we can expect that it will run, during the recursive calls, with nearly the same run time as a sorted array. That is, the run time for reverse sorted input is O(nlog(n)).

As the hint suggests, create an array of length 2^16 = 65,536. Let's call this the "count array". The value at a given index in the count array represents the number of times a value equal to that index has been seen in the input array. For example, index 1 in the count array holds the number of times the value 1 has been seen in the input.

As such, it is necessary to initialize all values in the count array to 0. Then, we use each value from the input as an index into the count array, incrementing the value in the count array at that index.

We can then rebuild the sorted array by scanning through the count array from low to high, creating the specified number of copies of the current index in the input array. For example, if our count array has a value of 2 at index 0 and a value of 3 at index 1, we would fill the first two spots in the input array with 0's and the next 3 with 1's, and so on.

Let's look at an example, with the number of bits reduced from 16 to 2:
Input: [2, 3, 2, 0, 1, 2, ...]
Count: [0, 0, 0, 0], start
Count: [0, 0, 1, 0], input index = 0
Count: [0, 0, 1, 1], input index = 1
Count: [0, 0, 2, 1], input index = 2
Count: [1, 0, 2, 1], input index = 3
Count: [1, 1, 2, 1], input index = 4
Count: [1, 1, 3, 1], input index = 5
...

Now we reconstruct the array:
Input: [0, 1, 2, 2, 2, 3, ...]

The method described is highly general - It can handle (many) duplicate values in the input and input arrays (much) larger than 2^16 elements - and has a run time of O(n). Specifically, construction of the count array can be considered constant time, the first scan through the input array costs n, and the "reconstruction" scan costs another n, leading to a run time of O(n).

Problem8Point15.java

public class Problem8Point15
{
      private static void sortShort(short[] numbers)
      {
         int numberCounts[] = new int[Short.MAX_VALUE + 1];

         // Initialization of the "count array"
         for (int currentCountsIndex = 0;
              currentCountsIndex < numberCounts.length;
              currentCountsIndex ++)
         {
            numberCounts[currentCountsIndex] = 0;
         }

         // Scan the input
         for (int currentNumbersIndex = 0;
              currentNumbersIndex < numbers.length;
              currentNumbersIndex ++)
         {
            numberCounts[numbers[currentNumbersIndex]] ++;
         }

         int currentNumbersIndex = 0;

         // "Reconstruct" the sorted array
         for (int currentNumber = 0;
              currentNumber < numberCounts.length;
              currentNumber ++)
         {
            int currentNumberCount = numberCounts[currentNumber];

            for (int currentNumberCopy = 0;
                 currentNumberCopy < currentNumberCount;
                 currentNumberCopy ++)
            {
               numbers[currentNumbersIndex] = (short)currentNumber;

               currentNumbersIndex ++;
            }
         }
      }

      public static void main(String[] arguments)
      {
         short[] numbers = new short[arguments.length];

         for (int currentNumberIndex = 0;
              currentNumberIndex < arguments.length;
              currentNumberIndex ++)
         {
            numbers[currentNumberIndex] =
               Short.parseShort(arguments[currentNumberIndex]);
         }

         System.out.println("Input is:");
         printArray(numbers);

         sortShort(numbers);
         
         System.out.println("Output is:");
         printArray(numbers);
      }      

      public static void printArray(short[] numbers)
      {
         final String DELIMITER = " ";

         for (int currentIndex = 0;
              currentIndex < numbers.length;
              currentIndex ++)
         {
            System.out.print(numbers[currentIndex] + DELIMITER);
         }
         System.out.println();
      }
}

The fairly obvious solution is to try every combination of numbers and see if they sum to the desired value (k). This approach costs O(n^2) (the analysis should be fairly obvious to the reader).

As the hint suggests, we might begin by sorting the numbers. This costs O(nlog(n)). The hint also suggests that, after sorting, we can answer the question in linear time. Let's first look at a way to do it in O(nlog(n)). Specifically, for each value in the array n1, we check to see if there is a value n2 such that (n1 + n2) = k. The outer loop ("for each value n1 in the array") is linear. The inner portion (finding if n2 exists in the array) can be done using binary search, which costs log(n). Therefore, we determine if a pair of numbers whose sum is k exists in the array in O(nlog(n)). Since both phases of the solution cost O(nlog(n)), the overall cost is O(nlog(n)).

In this version, we follow the hint and only spend linear time on the post-sorting phase of the solution. The underlying idea is that we only look at pairs of numbers that can possibly sum to k, and skip all other pairs.

The actual implementation uses two pointers, "high" and "low". Initially, low points to the lowest value in the array (to the lowest index) and high to the highest. At each iteration, the sum is taken of the two values pointed to by high and low. If the sum is greater than k, then high is moved to a lower index (where lower values reside). If the sum is less than k, then low is moved to a higher index. The algorithm stops either when a pair of numbers is found that sums to k, or when the low pointer has "passed" the high pointer (ie the low pointer has a higher index than the high pointer).

The analysis of the run time of this algorithm is straightforward. Each pointer moves only in one direction (ie they proceed monotonically) and the algorithm gurantees that one of these pointers will move exactly one position each iteration. The algorithm halts either when a sum is found, or, in the worst case, when the pointers pass each other. This latter case requires that the pointers traverse a total distance of n elements (each starting at opposite ends of the array and having to meet somewhere "in the middle"). Therefore, the run time of the post-sort phase is O(n) and the overall run time is O(nlog(n)).

public class Problem8Point19
{
      public static void searchForSum(int[] numbers, int desiredSum)
      {
         int lowIndex = 0;
         int highIndex = numbers.length - 1;

         while (lowIndex < highIndex)
         {
            int currentSum = numbers[lowIndex] + numbers[highIndex];

            if (currentSum == desiredSum)
            {
               System.out.println("Found sum!");
               System.out.println(numbers[lowIndex] + " (at index " +
                                  lowIndex + ") + " + numbers[highIndex] +
                                  " (at index " + highIndex + ") = " +
                                  currentSum);

               return;
            }
            else if (currentSum < desiredSum)
            {
               lowIndex ++;
            }
            // Must be currentSum > desiredSum
            else
            {
               highIndex --;
            }
         }

         System.out.println("Sum not found!");
      }

      public static void main(String[] arguments)
      {
         if (arguments.length <= 0)
         {
            return;
         }

         int desiredSum = Integer.parseInt(arguments[0]);

         int[] numbers = new int[arguments.length - 1];

         for (int currentNumberIndex = 0;
              currentNumberIndex < (arguments.length - 1);
              currentNumberIndex ++)
         {
            numbers[currentNumberIndex] =
               Integer.parseInt(arguments[currentNumberIndex + 1]);
         }

         System.out.println("Input is:");
         printArray(numbers);

         MergeSort sorter = new MergeSort();

         numbers = sorter.sort(numbers);
         
         System.out.println("Sorted array is:");
         printArray(numbers);

         searchForSum(numbers, desiredSum);
      }      

      public static void printArray(int[] numbers)
      {
         final String DELIMITER = " ";

         for (int currentIndex = 0;
              currentIndex < numbers.length;
              currentIndex ++)
         {
            System.out.print(numbers[currentIndex] + DELIMITER);
         }
         System.out.println();
      }      
}

I've done my best to write up correct solutions, but I'm only a computer and I sometimes make mistakes. If you think you have found one, please post to the newsgroup or email me.