I need help with 3, 5 and 6.

3. When using separate chaining to handle collisions within a hash table T, suppose we insist on representing each chain as a sorted array, and that a linear-time merge procedure is performed whenever a newly hashed element is inserted into the chain. If T has load factor , then provide big-O expressions for the average time it will take to i) successfully find an element in T, and ii) unsuccessfully find an element in T. Explain 4. Suppose that we are storing a set of m keys into a hash table of size n. Show that if the keys are drawn from a universe having size that exceeds mn, then there is a subset of m keys that all hash to the same slot; so that the worst-case searching time for separate-chaining hashing is (m) 5. Suppose we want to determine if the string s- 3182 .. Sk is a substring of the much larger string ala2 an. One approach is to compute h(s) with some hash function h. Then, for each i - 1,2,...,n- k +1, compute h(a,a1 .-aj+k-1). If this value is identical to h(s), then compare this string with s, and return true if the strings are identical. Otherwise, proceed to the next substring. Argue that the running time of this algorithm is O(k(n - k)). Prove that, if we assume the hash function is h(20..-z)-=0x1-i37", then the running time can be reduced to 0(n). Hint: argue that h(ai+M4+2 . . . ai+x) can be computed in (1) steps assuming h(ajaiti .-ai+-k-1) has been computed 6. Given two lists of integers of sizes m and n respectively, describe an algorithm that runs in time O(m+n) that computes the intersection of the lists. Argue that your algorithm is correct, and has the desired running time