While, considering the NUMBER PARTITION problem. As input, the number partition problem takes a sequence A = (a1, a2, . an) of non-negative integers,...

(10, 8, 7, 6, 5) → (2, 0, 7, 6, 5) → (2, 0, 1, 0, 5) → (0, 0, 1, 0, 3) → (0, 0, 0, 0, 2).

Prove that there is a partition that achieves the residue computed by the KK algorithm. Then implement the KK algorithm (you need not compute the partition, just the residue), and justify your algorithm's running time. You should strive to obtain an O(n log n) implementation.

(c.) Run several experiments for each of your implementations head-to-head on sets of 100 integers chosen uniformly starting from the range [1, 1000] and working up to the range [1, 1012] by powers of 10. Make sure to use 64-bit integers, and make sure the random number generator is working correctly on ranges this large. Point out where the pseudopolynomial-time algorithm from part (a) runs too slowly to be useful any more, and describe any differences you see in results obtained by the KK heuristic versus the exact algorithm.