Pete's Log: algorithms final problem
Entry #1029, (Coding, Hacking, & CS stuff)(posted when I was 22 years old.)
So sometime on Wednesday I went to ask Dr Chen if I could get back my algorithms final. He couldn't give it back to me, apparently due to some university regulations, but he let me make copies of it, which is more than good enough for me. I goofed up on two of the problems, resulting in a 106/120 on the final. Dr Chen spared a little time to inform me of the proper solution to the first problem, which I found rather interesting.
The problem was as follows: given that the 2-partition problem is NP-complete, prove that the i-partition problem is NP-complete. My solution was simply to reduce the 2-partition problem to the i-partition problem as follows: just plug the input set of the 2-partition problem into the i-partition problem with i=4, then group the 4 resulting partitions into 2 partitions. Well, this don't work so well for two reasons, it turns out. First, this won't always work, since there are sets for which there exist 2-partitions but for which there are no 4-partitions: {1, 1, 2} is an example. Second, this would only prove the 4-partition problem to be NP-complete, but not the i-partition problem for an arbitrary i. So the real reduction to use is to set x = the sum of all the numbers in the input set, divided by 2. Then, create a new set by adding (i-2) copies of x to the input set. Then use that as the input set for the i-partition problem. This will give you i partitions of size x. So now all you need to do is remove the (i-2) of these partitions that consist only of the number x, and then you've got your solution to the 2-partition problem. Very cool. I don't know if I could have come up with that solution on my own during the time we had for the test. Algorithms is cool.
so after all that was said and done, I thanked Dr Chen again for an excellent class, and he proceeded to inform me that I'd been an excellent student and had gotten the highest score in the class. My ego does enjoy a good feeding from time to time.