Exercises
-
In a jump search algorithm, the optimum number of jumps required to attain the minimum cost of comparisons is
, where n is the length of the input vector. Can you derive it? Also, what is the cost of comparison for the worst case, when the number of jumps is .
Evaluate the cost of searching an unsorted and a sorted (sorting based on frequency) vector, where each element has an equal probability of being accessed during the search operation, under the following conditions:
pi = 1/n, where i is the element in the given vector
pi = 1/n2 , where i is the element in the given vector
pi = 1/2n , where i is the element in the given vector
Implement the hash function in R using the mid-square method for four-and six-digit integers.
Implement the dictionary ADT using a hash table.
