CIS 554 Sorting Into Equal Piles
Fall 2014, David Matuszek

Purposes of this assignment

General idea of the assignment

Given a list of numbers, separate the numbers into two piles, such that the sum of the numbers in each pile is the same. For example, given the list [4, 6, 7, 9, 10, 12, 13, 19, 20], in which the numbers sum to 100, a possible solution is {[4, 6, 9, 12, 19], [7, 10, 13, 20]}, in which each of the two lists sum to 50.

Details

This is an NP-complete problem, which means that it is likely to take exponential time. Hence, if you break the problem up properly and use concurrency, you may get significant speedup on a dual-core or quad-core machine.

It would be interesting to time a sequential solution to this problem, and compare the time to that of a concurrent solution. However, we won't be doing that for this assignment; we'll just do the concurrent version, and not bother with timings.

You should prepare (by hand) some sample problems with which to try out your program. It's easy to generate problems that have a solution (although it's very hard to guarantee that the solution is unique). Probably 20 or 25 numbers in total is about the maximum length of list to work with.

To generate problems that do not have a solution, you can work with some very small lists, or with lists that sum to an odd number (so that no solution is possible).

Where do actors come in? Here's one possible way: Each time you have to decide whether to put a number into the first list or into the second list, you could put it into the first list, and spawn off an actor to put it into the second list. Then you and the other actor could proceed from there. You shouldn't do this every time, of course, or you might end up with 220 actors!

That's just one suggestion. However you do it, try to keep the actors down to a reasonable number--say, between 10 and 1000.

Put your program on a file named piles.erl. It should have a function named equalize which takes a list of integers as a parameter, and produces a tuple of two lists as a result (if successful) or the atom fail (if unsuccessful). Any problem which takes more than 20 seconds should return fail.

Include unit tests for all your functions.

Due date

Turn your assignment in to Canvas before 6am Wednesday, October 1.