Topic: Discrete Mathematics and its Applications" Chapter 9:Equivalence Relations and Partial Orderings.
Answer to (a):
The number different binary string of length n = 2n and the number different binary string of length k = 2k
So we need to map 2n strings to 2k strings.
When n > k, then each of 2k strings will be mapped on average by 2n/2k strings out of 2n strings.
Therefore, the average cardinality of the equivalence class [s]H = 2n/2k = 2n-k
Answer to (b):
The number of equivalence class = 2k
So the probability of a random string to be a member of a particular equivalence class = 1/2k = 2-k
Therefore, the probability for any two random strings such that [s]H = [t]H= 2-k
NB: Hope it helps to get your answer. Let me know any concern.
Topic: Discrete Mathematics and its Applications" Chapter 9:Equivalence Relations and Partial Orderings. 9. hash function H...
0. Introduction. This involves designing a perfect hash function for a small set of strings. It demonstrates that if the set of possible keys is small, then a perfect hash function need not be hard to design, or hard to understand. 1. Theory. A hash table is an array that associates keys with values. A hash function takes a key as its argument, and returns an index in the array. The object that appears at the index is the key’s...