2.4 Should Tables be Sorted? (20 pts) In class we saw universal hashing as the solution to processing N elements in the range (0,1,.... u - 1), arriving one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for any of these items can be processed in worst case O(1 time (so no uncertainty or expectation here)? In this problem you will design a solution for this, again using universal hashing. You are given a set S of N items in the range {0,1,..,un advance. Consider the following algorithm that stores these items into a table of size N2 2.4 Should Tables be Sorted? (20 pts) In class we saw universal hashing as the solution to processing N elements in the range (0,1,.... u - 1), arriving one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for any of these items can be processed in worst case O(1 time (so no uncertainty or expectation here)? In this problem you will design a solution for this, again using universal hashing. You are given a set S of N items in the range {0,1,..,un advance. Consider the following algorithm that stores these items into a table of size N2