|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
howManyNumbersintegers 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
solve works correctly. Add this test to the existing
unit tests. Try it with a stub version of
solve (which should fail
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
For best results (suggested, not required),
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
7 numbers add up to
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.]
mainmethod to solve a few simple problems, then solve and compute statistics for a bunch of other problems, as listed above.
readme.txtfile to present your results.
Tuesday, January 25, before midnight.