CIT 594 Assignment 2: Sorting into equal piles
CIT 594, Spring 2005


General Idea

Given an array of integers, sort them into three piles (pile A, pile B, and pile C) such that the sum of the numbers in each pile is the same. Write an equation that describes the running time of your program.


I will supply a class EqualPiles with the following method:

public static int[] createProblem(int howManyNumbers)
Returns an array of howManyNumbers integers that add up to 30000. These numbers can be sorted into three equal piles; the numbers in each pile will add up to 10000.

You will write a solve method (described below) that will take a problem and return a solution. But first, start by creating a JUnit test to determine whether solve works correctly. Add this test to the existing unit tests. Try it with a stub version of solve (which should fail the test).

Once solve is working, write a main method and any additional methods you like to do the following:

Avoid writing redundant code. The code needed is practically identical for each set of problems. Don't repeat the same several lines for each problem size.

To compute the time required, use the method System.currentTimeMillis(), like this:

long startingTime = System.currentTimeMillis();
code that you want to time
long endingTime = System.currentTimeMillis();
long timeRequired = endingTime - startingTime

For best results (suggested, not required),

Use backtracking

The solve method should be written as a backtracking algorithm. Here's the basic idea:

If, at any time, putting a number in a pile causes the pile to exceed 10000, you can report failure immediately, without recurring any further. If done properly (preferably without redoing the addition each time), this can speed up your algorithm enormously.

Caution: If you get the correct sum in one pile, that does not guarantee that it is part of a solution. For example, suppose you had the problem [6, 2, 5, 8, 2, 4, 3]. These 7 numbers add up to 30, and they can be sorted into 3 equal piles, as follows: [6, 4], [8,  2], [5,  3,  2], each of which adds up to 10 (that is, 30/3). However, if you construct the pile [6, 2, 2], that pile does add up to the correct value, but there is no way to arrange the remaining numbers [5, 8, 4, 3] into equal piles.

Finally, write a text file named readme.txt and include it with your program. On this file, summarize your results and try to define an equation that more or less describes your data. Is it linear (in the array size), quadratic, cubic, exponential, or what? [Don't spend a lot of time refining your equation to get the best possible fit; just try for a halfway reasonable first approximation.]


Due date:

Tuesday, January 25, before midnight.