Problem 3. Given an array A[1 : n] of a combination of n positive and negative integers, our goal is to find whether there is a sub-array A[l : r] such that Xr i=l A[i] = 0. Example. Given A = [13, 1, 2, 3, 4, 7, 2, 3, 8, 9], the elements in A[2 : 8] add up to zero. Thus, in this case, your algorithm should output Yes. On the other hand, if the input array is A = [3, 2, 6, 7, 20, 2, 4], then no sub-array of A adds up to zero and thus your algorithm should output No. Hint: Observe that if Pr i=l A[i] = 0, then Pl1 i=1 A[i] = Pr i=1 A[i]; this may come handy!(a) Suppose we are promised that every entry of the array belongs to the range {5, 4, . . . , 0, . . . , 4, 5}. Design an algorithm for this problem with worst-case runtime of O(n). (15 points) Hint: Counting sort can also be used to efficiently sort arrays with negative entries whose absolute value is not too large; we just need to shift the values appropriately. (b) Now suppose that there is no promise on the range of the entries of A. Design a randomized algorithm for this problem with expected worst-case runtime of O(n). (10 points)

Problem 3. Given an array A[1:n) of a combination of n positive and negative integers, our goal is to find whether there is a sub-array A[l: r] such that A[i] = 0. i=1 Example. Given A = [13, 1, 2, 3, -4, -7,2, 3, 8, 9), the elements in A[2 : 8] add up to zero. Thus, in this case, your algorithm should output Yes. On the other hand, if the input array is A = [3,2,6, -7, -20,2,4], then no sub-array of A adds up to zero and thus your algorithm should output No. Hint: Observe that if = A[i] = 0, then I'=1 A[i] = {=1 A[i]; this may come handy! 2 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. (a) Suppose we are promised that every entry of the array belongs to the range {-5, -4,...,0,...,4,5). Design an algorithm for this problem with worst-case runtime of O(n). (15 points) Hint: Counting sort can also be used to efficiently sort arrays with negative entries whose absolute value is not too large; we just need to "shift" the values appropriately. (b) Now suppose that there is no promise on the range of the entries of A. Design a randomized algorithm for this problem with expected worst-case runtime of O(n). (10 points) Problem 3. Given an array A[1:n) of a combination of n positive and negative integers, our goal is to find whether there is a sub-array A[l: r] such that A[i] = 0. i=1 Example. Given A = [13, 1, 2, 3, -4, -7,2, 3, 8, 9), the elements in A[2 : 8] add up to zero. Thus, in this case, your algorithm should output Yes. On the other hand, if the input array is A = [3,2,6, -7, -20,2,4], then no sub-array of A adds up to zero and thus your algorithm should output No. Hint: Observe that if = A[i] = 0, then I'=1 A[i] = {=1 A[i]; this may come handy! 2 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. (a) Suppose we are promised that every entry of the array belongs to the range {-5, -4,...,0,...,4,5). Design an algorithm for this problem with worst-case runtime of O(n). (15 points) Hint: Counting sort can also be used to efficiently sort arrays with negative entries whose absolute value is not too large; we just need to "shift" the values appropriately. (b) Now suppose that there is no promise on the range of the entries of A. Design a randomized algorithm for this problem with expected worst-case runtime of O(n). (10 points)