1. Let S be a set of n keys being mapped to a hash table (also) of size n. Find the expected number of empty slots under uniform hashing assumption. 2. Let S be a set of n keys being mapped to a has table of size n under chaining. Let X denote the length of longest chain in any slot. Show that the expected value E[X] = O(logn). 3. A string is palindromic if it is equal to its reverse. e.g.,abcabacba. Given a string T[1..n], find the largest palindromic suffix of this string in O(n) time. 4. Let T[1..n] be the text drawn from alphabet set E. Now, given i we want to find the lexi- cographic rank of suffix T[i..n] among all the suffixes of T. Give an O(n) algorithm for this task which does not involve building a suffix array or suffix tree. 5. Let T[1..n] be the text drawn from alphabet E. Our task is to construct an LCP array. LCP stands for longest common prefix. LCP array aids SA (suffix array) in doing faster binary search. LCP array is defined as LCP[i] = length of the longest common prefix of T[SA[i]..n] and T[SA[i+1]...n]. For example, for acacaac#, SA = = [8,5,6,3, 1, 7, 4, 2] and LCP = [0, 1,2,3,0, 1,2]. Given a suffix tree show an algorithm which can compute LCP in O(n) time. Assume that the suffix tree has edge labels which are in terms of two integers: starting and ending locations of the substring in T. Clearly describe what fields you would maintain in the "Node" structure and give a precise pseudocode based on tree traversal. Note that this is an implementation-level question so you must give a pseudocode. Just a high level description is not sufficient.