# Question

Consider a version of the division method in which h (k) = k mod m, where m = 2p – 1 and k is a character string interpreted in radix 2p. Show that if string x can be derived from string y by permuting its characters, then x and y hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.

## Answer to relevant Questions

Define a family ℋ of hash functions from a finite set U to a finite set B to be ¬-universal if for all pairs of distinct elements k and l in U, Pr {h(k) = h(l)} ≤ ¬, where the probability is taken over the ...Let us define a relaxed red-black tree as a binary search tree that satisfies red- black properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed red-black tree T whose root is red. ...Case 2 falls through into case 3, and so these two cases are not mutually exclusive.VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axis), so that a representation of a rectangle consists of ...Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers.Post your question

0