CIT 594 Assignment
2: Sorting into equal piles CIT 594, Spring 2005 
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:

For best results (suggested, not required),
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
. These 7
numbers add up to 30
,
and they can be sorted into 3
equal piles, as follows:
, each of
which adds up to 10
(that is, 30/3
). However, if you
construct the pile
, that pile does add up
to the correct value, but there is no way to arrange the remaining numbers
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.]
solve
method.main
method to solve a few simple problems, then solve
and compute statistics for a bunch of other problems, as listed above.readme.txt
file to present your results.Tuesday, January 25, before midnight.