Hash table to store a set #3

We want a data structure that supports the Set ADT:

• You can insert a new item in the set, which does nothing if the item is already there.
• You can test membership to find out if a given element is in the set or not.

In class we came up with the following idea: use a hash table of boolean values, initially all set to "false". When you "insert" an item \(x\) into the set, you compute the hash value of that element \(h(x)\), and then set the entry at position \(h(x)\) in the hash table to "true". Testing membership of an element \(y\) is then just looking at position \(h(y)\) in the table and seeing whether that table entry is set to "true".

I'm going to ask some questions about this idea as a series of problems. You can turn these in all on the same page, but please number each problem very clearly if you do.

Question 3: Suppose the size of the hash table is \(s=100\), there are \(n=20\) insertions, and \(m=20\) membership tests. Assuming that a perfectly random hash function is used, and that exactly half of the membership tests are for things that are actually in the set (and half are for things that aren't), what is the probability that there is at least one INCORRECT answer to the membership tests?