COS 226 Programming Assignment 9

Subset sums

Consider the square roots of the numbers from 1 to 100. Write a program to divide them into two sets A and B having the property that the sum of the numbers in set A is as close as possible to the sum of the numbers in set B.

Unlike previous programming assignments, there is no algorithm given in the book for this problem, nor will one be recommended here. Indeed, this is an NP-complete problem, so that finding the best possible answer would seem to require checking all possibilities. On the other hand, there are many heuristics that can lead to good answers, especially if efficient algorithmic tools are used. Depending on the heuristics that you choose, you may need to implement a sorting routine, hash table, search tree, priority queue, trie, or some other data structure that you have learned.

Use double-precision floating-point numbers in calculating the square roots and the subset sums.

If you make use of certain mathematical facts in the development of your solution, be sure that you state them, along with some justification, in your writeup. It is not necessary for you to provide proofs; something that you think might be true might be a heuristic that leads to a good solution, even if you can't prove it.

Your program should first print the difference in the sums of the subsets on the first line, then the numbers (not their square roots) in the set containing 1 on subsequent lines, 15 per line.

Your task is not only to design and implement an algorithm for this problem, but also to exercise good judgment in consuming CPU cycles and, as usual, providing a convincing explanation of your method and rationale for important design and implementation decisions.