CIT 594 Timing Methods
Spring 2009, David Matuszek

Purposes of this assignment:

• To get you to do some analysis of algorithms
• To give you some experience in timing methods
• To get you to think about algorithms

General idea of the assignment:

In this assignment you are to write four methods, analyze them (determine their Big-O running time), time them to see whether the numbers you get agree with your analysis, and JUnit test them. The four methods are:

public boolean subset1(int[] sub, int[] super)

Tests whether array sub is a subset of array super. Both sub and super are unsorted arrays.

public boolean subset2(int[] sub, int[] super)

Tests whether array sub is a subset of array super. Array sub is unsorted, super is sorted.

public boolean subset3(int[] sub, int[] super)

Tests whether array sub is a subset of array super. Both sub and super are sorted arrays.

public int[] findSubset(int[] numbers, int target)

Find and return a subset of numbers such that the sum of the numbers in the subset is exactly equal to target. You may assume that at least one solution exists.

In each case, find the fastest algorithm (in Big-O terms) for doing the job. Do not use Java's Set collection; do everything with arrays.

When you turn in the program, include a readme.txt file presenting your results. This file should include an analysis of each method, giving both your Big-O formula and a brief explanation of how you arrived at this formula. It should also include actual timing output from your program. (Since you should copy at least some of the output of your program and paste it into your writeup, please make the output self-explanatory.)

Supplied code:

The following method can be used to create "random" arrays. It can also be used to create "random" arrays of differing sizes, such that the smaller array is a prefix of the larger array.

/**
 * Creates an array of random numbers in the range 1 to <code>limit</code>.
 * No number will occur more than once in this array, but all calls with
 * the same value of <code>seed</code> will return the same sequence of
 * numbers, regardless of the size of the array.
 * 
 * @param size The size of the array to create.
 * @param limit All returned numbers will be less than or equal to this value.
 * @param seed A seed for the random number generator.
 * @return An array of unique random numbers.
 */
  public static int[] randomArray(int size, int limit, int seed) {
    assert size <= limit;
    java.util.Random rand = new java.util.Random(seed);
    int[] numbers = new int[size];
    outerLoop:
        for (int i = 0; i < numbers.length; i++) {
            int candidate = rand.nextInt(limit) + 1;
            for (int j = 0; j < i; j++) {
                if (numbers[j] == candidate) {
                    i--;
                    continue outerLoop;
                }
            }
            numbers[i] = candidate;
        }
    return numbers;
}

     System.out.println(Arrays.toString(randomArray(8, 100, 1234)));
     System.out.println(Arrays.toString(randomArray(12, 100, 1234)));

     [29, 34, 21, 11, 94, 30, 50, 98]
     [29, 34, 21, 11, 94, 30, 50, 98, 38, 61, 39, 48]

Hence, the shorter array is a prefix (and therefore, a subset) of the larger array. That's not exactly what we want for testing.

• For subset1, randomize one of the arrays (probably sub, since it may be shorter).
• For subset2, sort the super array.
• For subset3, sort both arrays.

For your timing tests, you can use only cases where the result will be true, since that is the worst case. (Your JUnit tests must, of course, test for both true and false results.)

You can use the following code to randomize an array:

/**
  * Randomizes an array in place.
  * 
  * @param array The array to be randomized (shuffled).
  */
 public static void randomize(int[] array) {
    java.util.Random rand = new java.util.Random();
    for (int i = array.length; i > 1; i--) {
        int choice = rand.nextInt(i);
        int temp = array[choice];
        array[choice] = array[i - 1];
        array[i - 1] = temp;
    }
}

For the findSubset method, you will need a means of generating problems that have at least one solution. I don't have exactly that code handy, but here is some more general code you can use.

/**
 * Divide a given number, <code>sum</code>, into <code>numbers</code>
 * addends, such that the addends sum to the given number, and the
 * addends can be partitioned into <code>piles</code> equal piles.
 * 
 * @param sum The number to be broken into addends.
 * @param numbers The desired number of addends.
 * @param piles The desired number of piles.
 * @return An array of numbers to be sorted into piles.
 */
public static int[] createProblem(int sum, int numbers, int piles) {
    check(sum >= numbers,
          "You can't have more numbers than their sum.");
    check(numbers >= piles,
          "You must have at least as many numbers as piles");
    check(sum % piles == 0,
          "The sum must be divisible by the number of piles");
    int[] result = new int[numbers];
    // Determine how many numbers to put into each pile (at least 1 each)
    int[] pileCounts;

    result = partitionNumber(sum, numbers, piles);
    randomize(result);
    return result;
}

/**
 * Throws an <code>IllegalArgumentException</code> if its boolean
 * input parameter is <code>false</code>.
 * 
 * @param b The parameter to test.
 * @param string The message to include in the <code>IllegalArgumentException</code>.
 */
private static void check(boolean b, String string) {
    if (b) return;
    throw new IllegalArgumentException(string);
}

/**
 * Separates a positive number into an array of positive numbers
 * (addends) which, when added, will yield the original number.
 * 
 * @param total The number to which the addends should sum.
 * @param numberOfNumbers How many addends are desired.
 * @param piles The number of equal piles that should be created.
 * @return The array of numbers that sum to <code>sum</code>.
 */
static int[] partitionNumber(int total, int numberOfNumbers, int piles) {
    int[] result = new int[numberOfNumbers];
    int[] cuts = new int[numberOfNumbers];
    
    // Insert initial cuts to make equal piles
    for (int i = 0; i < piles; i++) {
        cuts[i] = (i + 1) * (total / piles);
    }
    // Insert remaining cuts
    for (int i = piles; i < numberOfNumbers; i++) {
        // Choose each cut to be 0 < cut < sum
        cuts[i] = rand.nextInt(total - 1) + 1;
        // Ensure that the new cut is not the same as an existing cut
        for (int j = 0; j < i; j++) {
            if (cuts[j] == cuts[i]) i--;
        }
    }
    // Transform cuts into ranges
    Arrays.sort(cuts);
    result[0] = cuts[0];
    for (int i = 1; i < numberOfNumbers; i++) {
        result[i] = cuts[i] - cuts[i - 1];
    }
    return result;
}

With the above code, the call int[] numbers = createProblem(2000, 20, 2) will return an array of 20 numbers, such that some subset of them will add to 1000, and the remaining ones will also add to 1000. Hence, you are guaranteed that there are at least two solutions for findSubset(numbers, 1000).

Structure of the assignment:

• Project name: MethodTimings
• Package name: timings
• Class names and method signatures:
  • class Timings
    • public boolean subset1(int[] sub, int[] super)
    • public boolean subset2(int[] sub, int[] super)
    • public boolean subset3(int[] sub, int[] super)
    • public int[] findSubset(int[] numbers, int target)
• Provide JUnit tests for all of the above
  • If you care, here are the JUnit tests for the supplied code (Note: Uses JUnit 3).
• Provide Javadoc documentation for all classes and methods, except JUnit tests
  • Document JUnit tests if they are complex or do something non-obvious
• Name to use for Blackboard: MethodTimings_yourName

Grading:

You are expected to use good style (formatting, indentation, naming, etc.), document methods according to Javadoc conventions, and provide complete JUnit tests. In addition, you are expected to find the fastest algorithm (in Big-O terms) for each problem.

Due date: