Purposes

• To introduce the notion of analysis of algorithms
• To show you how to time programs

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.

Details

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:

• Generate a few small problems, and print the solutions. This gives us an additional check on whether your program works.
• Generate and solve:
  • 100 problems for 5 numbers;
  • 50 problems for 10 numbers;
  • 50 problems for 15 numbers;
  • 10 problems for 20 numbers; and
  • 5 problems for 25 numbers.
• For each array size, compute:
  • the average time in milliseconds required to solve a problem of this size;
  • the best (fastest) time for a problem of this size; and
  • the worst (slowest) time for a problem of this size.
  • Do not include in your measurements the time required to create the problem.
• For each array size, print out the best, average, and worst times. (You don't have to print out more than this, but you can if you like, so long as we can easily find this summary information.)

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),

• Minimize the number of other things that the computer is doing while you are timing your program. You can only measure the time elapsed; you cannot tell how much of that time was spent in your algorithm.
• Discard the worst time in each case. This is because Java occasionally performs garbage collection, and that may take hundreds of milliseconds. (If you were going over the numbers by hand, you would discard the worst time only if it was so much worse that you believed garbage collection had occurred.)

Use backtracking

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

• Set up three empty "piles" to put your numbers in (these can be arrays, Vectors, ArrayLists, or whatever you like).
• For each number in the problem,
  • Try putting it in the first pile, and recurring to solve the rest of the problem; if that doesn't work,
  • Try putting it in the second pile, and recurring to solve the rest of the problem; if that doesn't work,
  • Try putting it in the third pile, and recurring to solve the rest of the problem; if that doesn't work, report failure.
• If there are no more numbers to place, you have succeeded in solving the problem.

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.]

Summary:

• Add a JUnit test for your solve method.
• Write a main method to solve a few simple problems, then solve and compute statistics for a bunch of other problems, as listed above.
• Write a readme.txt file to present your results.

Due date:

Tuesday, January 25, before midnight.