Q1. (25 points - part (a) and (b) are purely written questions, part (c) requires implementation and code submission) In this question, you will analyze the empirical and theoretical collision probability for a new hash function.
The hash function h maps binary vectors of dimension m to binary vectors of dimension n, where m > n, with the help
of an n×m matrix H with binary elements that are generated randomly. More specifically, given the matrix H, the hash
function h : {0,1}
m → {0,1}
n provides the following hash value for a key x ∈ {0,1}
m :
where the mod operator is applied element-wise (to the obtained vector Hx).
For instance, if m = 3, n = 2, H is the matrix consisting of all ones, x is the vector of all ones, then the obtained vector
Hx will be the vector of all threes, and when the element-wise mod 2 is applied, the two-dimensional vector h(x) will be
obtained as the vector of all ones.
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
---|---|---|---|---|---|---|
27 | 28 | 29 | 30 | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |