4. 120 points] For any fixed integer k 2 2, the k-PARTITION PROBLEM (abbreviated 'k-PP') is: given a sequence of positive integers (wi,W2,. . . , wn), is it possible to partition them into k groups having equal sums. More formally, is there an n-vector h each of whose entries is a integer in the range 1,..., k such that, for each Wi Wii i-1 where h- [j]-(i | hli-j). For example, (1, 2, 1, 3, 1,1) is a "yes" instance of 3-PP, but a "no" instance of 4-PP: (3,2,1,3,3) is the reverse. (a) As in the previous problem, carefully show that k-PP is in NP. (b) Give an algorithm for k-PP and analyze its running time. 4. 120 points] For any fixed integer k 2 2, the k-PARTITION PROBLEM (abbreviated 'k-PP') is: given a sequence of positive integers (wi,W2,. . . , wn), is it possible to partition them into k groups having equal sums. More formally, is there an n-vector h each of whose entries is a integer in the range 1,..., k such that, for each Wi Wii i-1 where h- [j]-(i | hli-j). For example, (1, 2, 1, 3, 1,1) is a "yes" instance of 3-PP, but a "no" instance of 4-PP: (3,2,1,3,3) is the reverse. (a) As in the previous problem, carefully show that k-PP is in NP. (b) Give an algorithm for k-PP and analyze its running time