(Solved): (c) (6pts) We are maintaining a hash table as a single table without any chaining using a random h ...

(c) $(6\mathrm{pts})$ We are maintaining a hash table as a single table without any chaining using a random hash function $h$ from a suitable universal family $\mathcal{H}$. We do this by using a large table size $n^2$ in relation to the number of elements $n$ we expect to store at any point in time (e.g., as in the second level tables in the perfect hashing scheme we saw in class). The size of the universe $U$ is much larger than $n^2$, hence the need for hashing. With this simple scheme we respond to a search query by a user for an element $x$ with the value of $h(x)$ which gives the location at which $x$ is stored (if $x$ is in the table). The user then probes location $h(x)$ and either retrieves $x$ from location $h(x)$ or determines that $x$ is not in the table. Inserting or deleting an element $x$ is performed by placing $x$ at location $h(x)$ in the table or removing $x$ from location $h(x)$ in the table. In the highly unlikely event that a newly inserted element needs to be stored at the same location as an existing element, all elements in the table need to be re-hashed with a new random hash function, which an expensive operation. An adversary $A$ wishes to sabotage this set-up by forcing a collision through the insertion of 2 (specific) elements into the table. The family $\mathcal{H}$ is known to everyone, including the adversary, but the specific random hash function used for the table is not known to the adversary. (i) Establish that if $\mathcal{H}$ is a 2-universal family then w.h.p. in $n$ the adversary $A$ cannot accomplish his goal. (ii) Establish that the statement in (i) need not be true if '2-universal' is replaced by 'universal'. (For this, it suffices to establish that there is some universal family for which the adversary can achieve his goal.)