This problem examines a randomized algorithm for searching an unsorted array
A[1 . . . n] of n elements for a given value x. The strategy proceeds as follows. First, a ran-
dom index i ∈ {1, 2, . . . , n} is chosen. If A[i] = x, the procedure terminates and returns the
element A[i]. If A[i] 6= x, then the procedure generates another random index and the entire
process is repeated. The procedure terminates either when the target value is found (success),
or when all elements (indices) have been examined (failure). Therefore, we must keep track
of what indices were examined and what indices were not examined, although each time we
generate an index we do it at random without considering the history of examined elements.
Example runs:
Consider array
i 1 2 3 4 5
A[i] 4 20 15 12 3
Let’s say we are searching for x = 3. The sequence of indices until successful result may look
like this: 4, 2, 4, 3, 2, 1, 3, 5. This run would be successful (we found x = 3 on position 5). The
total number of iterations (trials) in this case would be 8.
On the other hand, let’s say we are searching for x = 7. The sequence of indices before failure
may look like this: 3, 1, 5, 2, 3, 2, 4. At this point, all indices would have been examined, and
therefore the result of the search would be failure. The total number of trials in this case
would be 7.

Your tasks:
(a) Suppose there is exactly one index i that contains the target value x (therefore, there
exists exactly one i for which A[i] = x). What is the expected number of iterations of the
random search strategy until the algorithm finds x You must count all iterations (even
those that query an already examined element of the array). Show the derivation (not
only the result). Hint: Use a recurrence for the expected number of trials T(n), and the
definition of the expected value.
(b) Implement the randomized search procedure, and perform 10,000 random searches for
each n ∈ {10, 20, 30, 40, 50}. In each of these runs, you should search an array of (ar-
bitrary) unique elements for one of its members (so that the results from part (a) are
accurately reproduced). At the end, for each n, output the average number of trials until
the value has been found. Your answer should approximately match the derivation from
part (a). Report your results in a table and submit the code (instructions at the end
of this assignment). If the results differ substantially from the results in (a), there is
probably some problem either with your derivation or with your code.
(c) This case is a generalization of case (a). Suppose there are k ≥ 1 indices for which the
array contains the target value x. How will the expected number of trials until successful
termination change compared to part (a) Show the derivation (not only the result).
(d) Suppose we are searching for a value that is not present in the array. What will be the
expected number of trials until we terminate with failure
(e) Modify the code from part (b) to simulate the scenario from part (d) (unsuccessful search),
and show the average numbers of trials for the different values of n ∈ {10, 20, 30, 40, 50}
(each time performing 10,000 random searches). These results should approximately
match the derivation from part (d). The code for this part should also be submitted.