1. Recall that in tabulation hashing we compute the hash function h(x) as the bitwise exclusive or T[0,x0]+T[1,x1]+...+T[i,xi]+... where T is a table of truly random numbers (all with the same number of bits as each other, and all independent from each other) and xi is the ith byte of x. Prove that tabulation hashing is 3-wise independent: any three input numbers are equally likely to map to any three output numbers. If it simplifies your analysis, you may assume that the inputs all have exactly four bytes, but you are not required to make this assumption. Hints: (1) consider separately the cases that there is a byte position i for which all three input numbers are different, or that there are positions in which two of them are the same and one is different. (2) Observe that if x and y have the same number of bits, x is fixed, and y is equally likely to be any value with that many bits, then their exclusive or x^y is also equally likely to be any value. (3) Choose some order to fix some of the table entries, so that with that order the first hash value can be shown to be equally likely to be any value, and then (once the first hash value is fixed) the second hash value can be shown to be equally likely to be any value, etc. 2. Suppose that we are building a Bloom filter to represent a set S of 1024 items, that we want each item to be mapped to five different positions in the Bloom filter, and that we want the probability of a false positive (that is, the probability that the query algorithm returns true for a fixed item x that is not actually in S) to be at most 1/1024. (a) What fraction of the cells in the table should be non-empty to achieve this false positive probability? (b) How many 32-bit words of memory should we allocate to the table, to be assured of getting this failure probability? (In answering this part, it's ok to overestimate the number of words needed, by assuming that no two members of S ever hash to the same location, and this assumption will simplify your analysis.) 3. Suppose that we are building a binary search tree T from an ordered list of n items (n > 1) by inserting them one at a time into T, without rebalancing, and that the insertion order is a random permutation of the input list (any permutation is equally likely to be chosen). (a) If x is either the smallest or the largest value in the input list, what is the probability that x is placed at a leaf of T? (Hint: suppose that x is the smallest value, and consider what happens when it is inserted before the second-smallest value, and what happens when it is inserted after the second-smallest value.) (b) If x is in the input list, but is neither the smallest or the largest value in the list, what is the probability that x is placed at a leaf of T? (c) What is the expected number of leaves of T, as a function of n?