CIT 594 Assignment 2: Minimizing Big-O Running Time

Spring 2013, David Matuszek

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

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

runs in O(n log n) time,
while each call of

runs in
O(log n) time.

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)));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 * (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)`

.

- 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
- 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*

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.