Let [m] denote the set {0,1,...,m − 1}. For each of the following families of hash functio...

Let [m] denote the set {0,1,...,m − 1}. For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family.

(a) H = {ha1,a2 : a1, a2 ∈ [m]}, where m is a fixed prime and

Notice that each of these functions has signature ha1,a2 : [m]2 → [m], that is, it maps a pair of integers in [m] to a single integer in [m].

(b) H is as before, except that now m = 2k is some fixed power of 2.

(c) H is the set of all functions f : [m] → [m − 1].