Problems

1. Assuming it is possible to sort n numbers in O(nlogn) time, show that it is possible to solve the three-

way set disjointness problem in O(nlogn) time. (20 points)

2. An array A contains n integers taken from the interval [0,4n], with repetitions allowed. Describe an

efficient algorithm for determining an integer value k that occurs the most often in A. What is the

running time of your algorithm? (30 points)