CIT 594 Assignment 2: Minimizing Big-O Running Time
Spring 2013, 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 five 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`. Array `sub` is sorted, `super` is unsorted.
`public boolean subset4(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, try to 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.)

Note: If you use methods from `java.util.Arrays`, you can assume that each call of `public static void sort(int[] a)` runs in O(n log n) time, while each call of `public static int binarySearch(int[] a, int key)` runs in O(log n) time.

# 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;
}```
Example:
```     System.out.println(Arrays.toString(randomArray(8, 100, 1234)));
System.out.println(Arrays.toString(randomArray(12, 100, 1234)));```
produces:
```    [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
*
* @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 boolean subset4(int[] sub, int[] super)```
• ```public int[] findSubset(int[] numbers, int target)```
• Provide JUnit tests for all of the above
• 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`