Question

JAVA CODE

Write a JAVA program to do the following.

Input an integer x. (Should work with “big” numbers.)

Create a completely-skewed BST S containing 1, 2, . . . , x.

Create a BST R containing x integers without repetitions gen- erated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced.

Measure the time to search in S for a number that is not in the tree.

Measure the time to search in R for a new random number.

Display the time taken for each search.

Thank you in advance

Answer 1

Generate random numbers without repetitions

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

Randomized selection.

We return to finding the ismallest item for a fixed but arbitrary integer 1 ≤ i ≤ n, which we call the rank of that item. We can use the splitting function of quicksort also for selection. As in quicksort, we choose a random pivot and split the array, but we recurse only for one of the two sides. We invoke the function with the range of indices of the current subarray and the rank of the desired item, i. Initially, the range consists of all indices between ℓ = 1 and r = n, limits included.

int RSELECT(int ℓ, r, i)

q = RSPLIT(ℓ, r);

m = q − ℓ + 1;

if i < m

then

return RSELECT(ℓ, q − 1, i)

elseif i = m

then

return q

else return RSELECT(q + 1, r, i − m)

endif.

For small sets, the algorithm is relatively ineffective and its running time can be improved by switching over to sorting when the size drops below some constant threshold. On the other hand, each recursive step makes some progress so that termination is guaranteed even without special treatment of small sets. Expected running time. For each 1 ≤ m ≤ n, the probability that the array is split into subarrays of sizes m − 1 and n − m is 1 n . For convenience we assume that nis even.

The expected running time increases with increasing number of items, T (k) ≤ T (m) if k ≤ m.

Hence, T (n) ≤ n + 1 n Xn m=1 max{T (m − 1),

T (n − m)} ≤ n + 2 n Xn m= n 2 +1 T (m − 1).

Assume inductively that T (m) ≤ cm for m < n and a sufficiently large positive constant c. Such a constant c can certainly be found for m = 1, since for that case the running time of the algorithm is only a constant. This establishes the basis of the induction. The case of n items reduces to cases of m < n items for which we can use the induction hypothesis.

We thus get T (n) ≤ n + 2c n Xn m= n 2 +1 m − 1 = n + c · (n − 1) − c 2 · n 2 + 1 = n + 3c 4 · n − 3c 2 . Assuming c ≥ 4 we thus have T (n) ≤ cn as required. Note that we just proved that the expected running time of RSELECT is only a small constant times that of RSPLIT. More precisely, that constant factor is no larger than four.